数据结构练习题

一. 选择题(共15题,每题2分,共30分)

1. 算法分析的两个主要方面是（ A）。

A. 空间复杂度和时间复杂度 B. 正确性和简单性

C. 可读性和文档性 D. 数据复杂性和程序复杂性

2. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。

A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 3. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（ C ）。

A. O(log2n) B.O(1) C. O(n) D.O(n2) 4. 线性表L=(a1,a2,……,an)，下列说法正确的是（D ）。

A. 每个元素都有一个直接前驱和一个直接后继 B. 线性表中至少要有一个元素

C. 表中诸元素的排列顺序必须是由小到大或由大到小

D. 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继

5. 判断一个循环队列Q（最多n个元素）为满的条件是（C ）。

A. Q->rear==Q->front B. Q->rear==Q->front+1 C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n 6. 一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（ A ）。

A. *S->top=e;S->top++; B. S->top++;*S->top=e; C. *S->top=e D. S->top=e; 7. 广义表(a,b,c)的表尾是（ B ）。

A. b,c B. (b,c) C. c D. (c) 8. 稀疏矩阵一般的压缩存储方法有两种，即（ C ）。

A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表

9. 在一棵具有5层的满二叉树中结点总数为（ A）。 A. 31 B. 32 C. 33 D. 16

10. 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中，若结点R[i]有左孩子，则其左孩子是（ C ）。

A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i]

11. 对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（B ）。

A. n B. n2 C. n-1 D. (n-1)2 12. 设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1V2,E1E2则称（ A ）。

A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量

13. 已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（ A ）次。

A. 1 B. 2 C. 3 D. 4 14. 解决哈希冲突的主要方法有（ D ）。 A. 数字分析法、除余法、平方取中法 B. 数字分析法、除余法、线性探测法 C. 数字分析法、线性探测法、再哈希法 D. 线性探测法、再哈希法、链地址法

15. 在任何情况下，时间复杂度均为O(nlogn)的不稳定的排序方法是（C ）。 A.直接插入 B. 快速排序 C. 堆排序 D. 归并排序 二. 填空题(共10题,每题2分,共20分)

1数据结构按逻辑结构可分为两大类，它们分别是 和 。 2.设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句： 。

3.一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为： 。

4. 两个串相等的充分必要条件是两个串的长度相等且 。

5. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是 6. 广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： 。 7. 具有n个结点的完全二叉树的深度是 8. 在一棵二叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有n0= 9. 判定一个有向图是否存在回路，可以利用 。 10. 在散列存储中，装填因子α的值越大，则存取元素时发生冲突的可能性就越 ；α值越小，则存取元素发生冲突的可能性就越 。

三. 简答题（共6题，每题5分，共20分）

1. 函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype *e){ LinkList p；int j；

p=L->next;j=1;

while(p&&j}

if(!p||j>i) return ERROR; *e= (2) ; return OK; }

2. 已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，写出该二叉树的后序序列

并画出该二叉树。

3. 假设用于通信的电报仅由8个字母构成，字母在电文中出现的频率分别为0.07、0.19、

0.02、0.06、0.32、0.03、0.21和0.10. （1）构造出相应的哈夫曼树；(2)写出这个8个字母设计哈夫曼编码(（3）计算该哈夫曼树的加权路径长度

4. 下图为一无向图，请：（1）给出该无向图存储结构的邻接链表表示（邻接顶点请以顶

点序号递增排序，以使答案唯一）；（2）写出对其分别进行深度优先遍历的结果（从顶点1开始）。

12569738

4四. 程序题（共2题，每题10分，共20分）

1. 已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。写

出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc）。 2. 输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩

由高到低的次序输出（每行10个记录）。排序方法采用选择排序。

《数据结构（C语言版）》练习题答案

一 选择题：1-5：ABCDC 6-10：ABCAC 11-15：BAADC 二 填空题： 1.

线性结构和非线性结构 2. 答案：q->next=p->next p->next=q 3. 答案：(rear-front+M)%M 4. 对应位置字符相同 5. Loc(A[0][0])+(i*N+j)*k 6. (x,y,z)

7. log2n+1 8. n2+1 9. 拓扑排序 10. 大 ，小

三 判断题： 四 简答题

1 答案：(1)p=p->next (2)p->data

abd2.

cehfg后序序列为：debhfgca

10006002801105021316701171101321901401213.

（2） 频率 哈夫曼编码 0.07 0010 0.19 10 0.02 00000 0.06 0001 0.32 01 0.03 00001 0.21 11 0.10 011 （3）加权路径长度为2.61

12345678211122335357468˄ ˄ ˄ ˄ 99996˄ ˄ ˄ ˄ 784.

9˄ （2）深度优先的遍历序列为：125967384

五 程序题：

1.

LinkedList Union(LinkedList la, lb) ｛ pa=la->next;pb=hb->next;

lc=(LinkedList )malloc(sizeof(LNode)); pc=lc;∥pc是结果链表中当前结点的前驱 while(pa&&pb)

if(pa->datadata)

{pc->next=pa;pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} if(pa)pc->next=pa; else pc->next=pb;

free(la);free(lb);∥释放原来两链表的头结点。

}∥算法Union结束。

2. typedef struct

{ int num; float score; }RecType;

void SelectSort(RecType R[51]，int n) { for(i=1; i{ //选择第i大的记录，并交换到位

k=i; //假定第i个元素的关键字最大

for(j=i+1;j<=n;j++) //找最大元素的下标 if(R[j].score>R[k].score) k=j;

if(i!=k) R[i] <-->R[k]; //与第i个记录交换 }//for

for(i=1; i<=n; i++) //输出成绩

{ printf(\"%d,%f\}//SelectSort