1、数据结构真题 2013 年 1 月及答案解析(总分：85.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.数据的逻辑结构可以分为_ A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性结构 D.简单结构和构造结构（分数：2.00）A.B.C.D.2.线性表是一个有限序列，组成线性表的基本单位是_ A.数据项 B.数据元素 C.数据域 D.字符（分数：2.00）A.B.C.D.3.栈中有 a、b 和 c 三个元素，a 是栈底元素，c 是栈顶元素，元素 d 等待进栈，则不可能的出栈序列是_ A.dcba B.cbda C.cadb D.cdba
2、（分数：2.00）A.B.C.D.4.稀疏矩阵的三元组表是_ A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列表存储结构（分数：2.00）A.B.C.D.5.已知广义表 G，head(G)与 tail(G)的深度均为 6，则 G 的深度是_ A.5 B.6 C.7 D.8（分数：2.00）A.B.C.D.6.下列编码集合中，属于前缀编码的一组是_ A.11，10，001，101，0001 B.00，010，0110，1000 C.11，01，001，0101，0001 D.0，10，110，1011（分数：2.00）A.B.C.D.7.如下图所示二叉树的中序序列为_（分数：2.0
3、0）A.B.C.D.8.有向图中所有顶点入度之和与所有顶点出度之和的比是 A.1/2 B.1 C.2 D.4（分数：2.00）A.B.C.D.9.含有 n 个顶点和 e 条边的有向图的邻接矩阵中，零元素的个数是_ A.e B.2e C.n2-2e D.n2-e（分数：2.00）A.B.C.D.10.n 个顶点的无向连通图，其生成树的边数为_ A.n-1 B.n C.n+1 D.nlog2n（分数：2.00）A.B.C.D.11.用自底向上的冒泡排序方法对序列(8，13，26，55，29，44)从大到小排序，第一趟排序需进行交换的次数为_ A.2 B.3 C.4 D.5（分数：2.00）A.B.
4、C.D.12.对序列(8，13，26，55，29，44)从小到大进行基数排序，第一趟排序的结果是_ A.(13，44，55，26，8，29) B.(13，26，55，44，8，29) C.(8，13，26，29，44，55) D.(29，26，8，44，55，13)（分数：2.00）A.B.C.D.13.采用分块查找时，要求数据_ A.块内有序 B.分块有序 C.分块无序 D.每块中数据个数必须相同（分数：2.00）A.B.C.D.14.下列关于散列函数的说法正确的是_ A.散列函数越复杂越好 B.散列函数越简单越好 C.用除余法构造的散列函数是最好的 D.在冲突尽可能少的情况下，散列函数越简
5、单越好（分数：2.00）A.B.C.D.15.下列关于 m 阶 B 树的叙述中，错误的是_ A.每个结点至多有 m 棵子树 B.每个结点至多有 m-1 个关键字 C.所有的叶结点均在同一层上 D.根结点至少有 m/2 棵子树（分数：2.00）A.B.C.D.二、B填空题/B(总题数：10，分数：20.00)16.算法的时间复杂度与实现时采用的程序设计语言_。（分数：2.00）填空项 1:_17.在长度为 n 的顺序表的第 i(1in)个元素之后插入一个元素时，需向后移动_个元素。（分数：2.00）填空项 1:_18.设循环队列存放在向量 data0m-1中，在出队操作后，队头指针 front
6、变化为_。（分数：2.00）填空项 1:_19.树的前序遍历序列等同于该树对应二叉树的_遍历序列。（分数：2.00）填空项 1:_20.一个 10090 的整型稀疏矩阵有 10 个非零元素，设每个整型数占 2 个字节，则用三元组表存储该矩阵时，所需的字节数是_。（分数：2.00）填空项 1:_21.当用二叉链表作为 n 个结点的二叉树的存储结构时，空指针域的个数是_。（分数：2.00）填空项 1:_22.采用邻接表表示 n 个顶点的有向图时，若表结点的个数为 m，则该有向图的边数为_。（分数：2.00）填空项 1:_23.对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的
7、算法是_。（分数：2.00）填空项 1:_24.在 16 个记录的有序顺序表中进行二分查找，最大比较次数是_。（分数：2.00）填空项 1:_25.在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是_的。（分数：2.00）填空项 1:_三、B解答题/B(总题数：1，分数：5.00)判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。（分数：5.00）(1).(1，5，7，20，18，8，10，40)（分数：2.50）_(2).(18，9，5，8，4，17，21，6)（分数：2.50）_四、B算法阅读题/B(总题数：2，分数：20.00)单链表类型定
8、义如下：typedef struet nodeDataType data; struct node *next; ListNode; typedef ListNode *LinkList; 阅读下列算法，并回答问题：void f30(LinklList head, DataType x) /head 是带头结点的非空单链表的头指针ListNode *p, *q; p=head; while(p-next-next)p=p-next; q=(ListNode*)malloc(sizeof(ListNode); q-data=x; q-next=p-next; p-next=q; （分数：5.00
9、）(1).该算法的功能是什么?（分数：2.50）_(2).若单链表的长度为 n，算法的时间复杂度是多少?该时间复杂度和链表的初始状态有关吗?（分数：2.50）_阅读下列算法(假设栈的操作函数都已定义)，并回答问题：void f31_ SeqStaek S; char x, y; x=c; y=k; Push( Push( Push( x=Pop( Push( Push( X=Pop( Push( while(!StackEmpty( putchar(y);putchar(x);（分数：15.00）(1).自底向上写出执行 while 语句之前栈 S 中的元素序列。（分数：3.75）_(2).写
10、出该函数的最后输出结果。（分数：3.75）_(3).下列算法的功能是在中序线索树中查找结点*p 的前趋，填上适当内容使算法完整。 typedef enum Link, Thread PointerTag; /枚举值 Link 和 Thread 分别为 0 和 1 typedef struct node DataType data; PointerTag ltag, rtag; Struct node *lchild, *rchild; BinThrNode; BinThrNode*f32(BinThrNode *p) /在中序线索树中找结点*p 的中序前趋，设 p 非空 BinThrNode
11、*q; if(p-ltag=Thread)_; else q=p-lchild; while(q-rtag=Link)_; return q; （分数：3.75）_(4).分析下列排序算法中语句 1 和语句 2 的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。 void f33(int a, int n) int i, j, k, t; for(i=0; in; i+) /语句 1 j=i; for (k=j+1; k=n; k+) if(akaj)j=k; /语句 2 t=ai; ai=aj; aj=t; （分数：3.75）_五、B算法设计题/B(总题数：1，分数：10.00
12、)26.二叉排序树的类型定义如下： typedef struct node int data; struct node *lehild, *rchild; *BSTree; 编写递归算法从小到大输出二叉排序树 T 中所有 data 域值大于 m 且小于 n 的数据。 函数原型为 void f34(BSTree T, int m, int n)（分数：10.00）_数据结构真题 2013 年 1 月答案解析(总分：85.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.数据的逻辑结构可以分为_ A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线
13、性结构 D.简单结构和构造结构（分数：2.00）A.B.C. D.解析：考点 数据的逻辑结构包含的内容 解析 数据的逻辑结构可以分为线性结构和非线性结构。2.线性表是一个有限序列，组成线性表的基本单位是_ A.数据项 B.数据元素 C.数据域 D.字符（分数：2.00）A.B. C.D.解析：考点 本题考查的数据表的基本单位 解析 线性表是一个有限序列，组成线性表的基本单位是数据元素。3.栈中有 a、b 和 c 三个元素，a 是栈底元素，c 是栈顶元素，元素 d 等待进栈，则不可能的出栈序列是_ A.dcba B.cbda C.cadb D.cdba（分数：2.00）A.B.C. D.解析：考
14、点 栈的操作 解析 根据栈的操作原则，不可能的出栈序列是 cadb。4.稀疏矩阵的三元组表是_ A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列表存储结构（分数：2.00）A. B.C.D.解析：考点 稀疏矩阵的三元组表的存储结构 解析 稀疏矩阵的三元组表是顺序存储结构。5.已知广义表 G，head(G)与 tail(G)的深度均为 6，则 G 的深度是_ A.5 B.6 C.7 D.8（分数：2.00）A.B.C. D.解析：考点 广义表深度的计算 解析 当表头、表尾的深度相等时，广义表的深度为表头深度加 1。6.下列编码集合中，属于前缀编码的一组是_ A.11，10，001，
15、101，0001 B.00，010，0110，1000 C.11，01，001，0101，0001 D.0，10，110，1011（分数：2.00）A.B. C.D.解析：考点 前缀编码的判断 解析 根据前缀编码的概念，选项 B 可判断为前缀编码。7.如下图所示二叉树的中序序列为_（分数：2.00）A. B.C.D.解析：考点 二叉树的中序遍历 解析 根据二叉树中序遍历的方法，可得到所给二叉树的中序遍历为ACDB。8.有向图中所有顶点入度之和与所有顶点出度之和的比是 A.1/2 B.1 C.2 D.4（分数：2.00）A.B. C.D.解析：考点 有向图的入度与出度 解析 在有向图中，顶点总的
16、入度和出度是相同的，所以其比例为1。9.含有 n 个顶点和 e 条边的有向图的邻接矩阵中，零元素的个数是_ A.e B.2e C.n2-2e D.n2-e（分数：2.00）A.B.C.D. 解析：考点 图的邻接矩阵中零元素的个数解析 含有 n 个顶点和 e 条边的有向图的邻接矩阵中，零元素的个数是 n2-e。10.n 个顶点的无向连通图，其生成树的边数为_ A.n-1 B.n C.n+1 D.nlog2n（分数：2.00）A. B.C.D.解析：考点 无向图的边数的问题 解析 n 个顶点的无向连通图，其生成树的边数为 n-1。11.用自底向上的冒泡排序方法对序列(8，13，26，55，29，4
17、4)从大到小排序，第一趟排序需进行交换的次数为_ A.2 B.3 C.4 D.5（分数：2.00）A. B.C.D.解析：考点 冒泡排序算法中交换的次数 解析 根据冒泡排序的方法，可知给定序列第一趟排序的交换次数为 2。12.对序列(8，13，26，55，29，44)从小到大进行基数排序，第一趟排序的结果是_ A.(13，44，55，26，8，29) B.(13，26，55，44，8，29) C.(8，13，26，29，44，55) D.(29，26，8，44，55，13)（分数：2.00）A. B.C.D.解析：考点 基数排序 解析 根据基数排序的方法，第一趟先按个位数排序，得到排序结果为(
18、13，44，55，26，8，29)。13.采用分块查找时，要求数据_ A.块内有序 B.分块有序 C.分块无序 D.每块中数据个数必须相同（分数：2.00）A.B. C.D.解析：考点 分块排序的基本要求 解析 采用分块查找时，要求数据分块有序。14.下列关于散列函数的说法正确的是_ A.散列函数越复杂越好 B.散列函数越简单越好 C.用除余法构造的散列函数是最好的 D.在冲突尽可能少的情况下，散列函数越简单越好（分数：2.00）A.B.C.D. 解析：考点 散列函数的性质的判断 解析 在冲突尽可能少的情况下，散列函数越简单越好。15.下列关于 m 阶 B 树的叙述中，错误的是_ A.每个结点
19、至多有 m 棵子树 B.每个结点至多有 m-1 个关键字 C.所有的叶结点均在同一层上 D.根结点至少有 m/2 棵子树（分数：2.00）A.B.C.D. 解析：考点 B 树的特征的判断 解析 根结点(若不为叶子结点)至少有 2 棵子树，除根结点之外的所有非终端结点至少有 m/2 棵子树。二、B填空题/B(总题数：10，分数：20.00)16.算法的时间复杂度与实现时采用的程序设计语言_。（分数：2.00）填空项 1:_ （正确答案：无关）解析：考点 算法的时间复杂度与采用的设计语言的关系 解析 算法的时间复杂度与实现时采用的程序设计语言无关。17.在长度为 n 的顺序表的第 i(1in)个元
20、素之后插入一个元素时，需向后移动_个元素。（分数：2.00）填空项 1:_ （正确答案：n-i）解析：考点 顺序表中元素的插入问题 解析 在长度为 n 的顺序表的第 i(1in)个元素之后插入一个元素时，需向后移动 n-i 个元素。18.设循环队列存放在向量 data0m-1中，在出队操作后，队头指针 front 变化为_。（分数：2.00）填空项 1:_ （正确答案：加 1）解析：考点 循环队列的操作 解析 当队列执行出队操作时，其队头指针将加 1。19.树的前序遍历序列等同于该树对应二叉树的_遍历序列。（分数：2.00）填空项 1:_ （正确答案：前序）解析：考点 树的前序遍历与其对应的二
21、叉树的遍历的关系 解析 树的前序遍历序列等同于该树对应二叉树的前序遍历序列。20.一个 10090 的整型稀疏矩阵有 10 个非零元素，设每个整型数占 2 个字节，则用三元组表存储该矩阵时，所需的字节数是_。（分数：2.00）填空项 1:_ （正确答案：60）解析：考点 三元组表的存储问题 解析 稀疏矩阵共有 10 个非零元素，每个整型变量需要 2 个存储单元，共需 1032=60 个存储单元。21.当用二叉链表作为 n 个结点的二叉树的存储结构时，空指针域的个数是_。（分数：2.00）填空项 1:_ （正确答案：n+1）解析：考点 二叉链表的空链域的个数 解析 当用二叉链表作为 n 个结点的
22、二叉树的存储结构时，空指针域的个数是 n+1。22.采用邻接表表示 n 个顶点的有向图时，若表结点的个数为 m，则该有向图的边数为_。（分数：2.00）填空项 1:_ （正确答案：m）解析：考点 图的邻接表与图的对应关系 解析 有向图的邻接表中，表结点的个数等于有向图的边数。23.对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的算法是_。（分数：2.00）填空项 1:_ （正确答案：冒泡排序）解析：考点 排序方法的选择 解析 当待排序记录关键字基本有序时，宜采用直接插入排序或冒泡排序。24.在 16 个记录的有序顺序表中进行二分查找，最大比较次数是_。（分数：2.00）
23、填空项 1:_ （正确答案：33）解析：考点 二分查找的查找次数的计算 解析 在 n 个记录的有序顺序表中进行二分查找，最大比较次数是 2n+1。25.在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是_的。（分数：2.00）填空项 1:_ （正确答案：稳定）解析：考点 排序算法稳定性的概念 解析 在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。三、B解答题/B(总题数：1，分数：5.00)判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。（分数：5.00）(1).(1，5，7，20，18，8，10，
24、40)（分数：2.50）_正确答案：(不是大根堆，调整后的根堆为：(40，20，10，5，18，8，7，1)解析：(2).(18，9，5，8，4，17，21，6)（分数：2.50）_正确答案：(不是大根堆，调整后的大根堆为：(21，9，18，8，4，17，5，6)解析：考点 大堆的判定以及调整四、B算法阅读题/B(总题数：2，分数：20.00)单链表类型定义如下：typedef struet nodeDataType data; struct node *next; ListNode; typedef ListNode *LinkList; 阅读下列算法，并回答问题：void f30(Link
25、lList head, DataType x) /head 是带头结点的非空单链表的头指针ListNode *p, *q; p=head; while(p-next-next)p=p-next; q=(ListNode*)malloc(sizeof(ListNode); q-data=x; q-next=p-next; p-next=q; （分数：5.00）(1).该算法的功能是什么?（分数：2.50）_正确答案：(在单链表的表尾处插入结点 x)解析：(2).若单链表的长度为 n，算法的时间复杂度是多少?该时间复杂度和链表的初始状态有关吗?（分数：2.50）_正确答案：(算法的时间复杂度为 O
26、(n)，该时间复杂度与链表的初始状态无关)解析：考点 单链表的插入操作 解析 根据算法可知其为在单链表的表尾处插入结点 x 的算法，其时间复杂度为 O(n)，该时间复杂度与链表的初始状态无关。阅读下列算法(假设栈的操作函数都已定义)，并回答问题：void f31_ SeqStaek S; char x, y; x=c; y=k; Push( Push( Push( x=Pop( Push( Push( X=Pop( Push( while(!StackEmpty( putchar(y);putchar(x);（分数：15.00）(1).自底向上写出执行 while 语句之前栈 S 中的元素序列
27、。（分数：3.75）_正确答案：(执行 while 语句之前栈 S 中的元素序列为 c，a，t，s)解析：(2).写出该函数的最后输出结果。（分数：3.75）_正确答案：(该函数的最后输出结果为 stack。)解析：考点 栈的操作的应用 解析 通过阅读程序可知执行 while 语句之前栈 s 中的元素序列为c，a，t，s；该函数的最后输出结果为 stack。(3).下列算法的功能是在中序线索树中查找结点*p 的前趋，填上适当内容使算法完整。 typedef enum Link, Thread PointerTag; /枚举值 Link 和 Thread 分别为 0 和 1 typedef st
28、ruct node DataType data; PointerTag ltag, rtag; Struct node *lchild, *rchild; BinThrNode; BinThrNode*f32(BinThrNode *p) /在中序线索树中找结点*p 的中序前趋，设 p 非空 BinThrNode *q; if(p-ltag=Thread)_; else q=p-lchild; while(q-rtag=Link)_; return q; （分数：3.75）_正确答案：(return p-lchild q=q-rchild)解析：考点 以中序线索二叉链表作为存储结构，查找某结点
29、的中序前驱结点的算法 解析 根据题干中所给的算法的功能：在中序线索树中查找结点*p 的前驱，可填出空白语句。(4).分析下列排序算法中语句 1 和语句 2 的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。 void f33(int a, int n) int i, j, k, t; for(i=0; in; i+) /语句 1 j=i; for (k=j+1; k=n; k+) if(akaj)j=k; /语句 2 t=ai; ai=aj; aj=t; （分数：3.75）_正确答案：(语句 1 频度是 n语句 2 频度 n(n+1)/2该算法为直接选择排序，其时间复杂度为 O(
30、n2)。)解析：考点 直接选择排序的算法解析 根据算法，可判断出其为直接选择排序的算法，其时间复杂度为 O(n2)。五、B算法设计题/B(总题数：1，分数：10.00)26.二叉排序树的类型定义如下： typedef struct node int data; struct node *lehild, *rchild; *BSTree; 编写递归算法从小到大输出二叉排序树 T 中所有 data 域值大于 m 且小于 n 的数据。 函数原型为 void f34(BSTree T, int m, int n)（分数：10.00）_正确答案：(void f34(BSTree T, int m, int n) BSTNode *p; /定义指向树结点的指针 p=T; if (T=NULL) exit(0); if(mp-data) f34(p-lchild, m, n); f34(p-rchild, m, n) )解析：考点 输出二叉排序树中所有 data 域值大于 m 且小于 n 的数据的算法
