《数据结构》试卷第1套

1、数据结构试卷第1套三、单项选择题：(每小题1分，共5分)1 .对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为：A)顺序表B)用头指针表示的单循环链表C)用尾指针表示的单循环链表D)单链表2.假设以第一个元素为分界元素，对字符序列(Q, H, C, Y, P, A, M, S, R, D, F, X)进行快 速排序，则第一次划分的结果是：A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S, Y, X) C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P

2、, A, M, F, H, C, D, Q, S, Y, R, X) 3.下面是三个关于有向图运算的叙述：(1)求有向图结点的拓扑序列，其结果必定是唯一的(2)求两个指向结点间的最短路径，其结果必定是唯一的(3)求AOE网的关键路 径，其结果必定是唯一的其中哪个(些)是正确的？A)只有(1) B) (1)和(2) C)都正确 D)都不正确4.若进 栈序列为a, b, c,则通过入出栈操作可能得到的a, b, c的不同排列个数为：A) 4B) 5C) 6D) 7 5.以下关于广义表的叙述中，正确的是：A)广义表是由。个或多个单元素或子表构成的有限序列B)广义表至少有一个元素 是子表0广义表不能递

3、归定义D)广义表不能为空表四、填空题：(每小题2分，共20分)1. 一棵含有101个结点的完全二叉树存储在数组AL. 101中，对lWkWlOl,若 Ak是非叶结点，则k的最小值是：，k的最大值是：o 2.设s=' YOU ARE JUDGING IT RIGHT OR WRONG, ,顺序执行下列操作：SubString (subl, s, 1, 8) ; SubString (sub2, s, 20, 5) ; StrCat (subl, sub2);则最后 subl的值为：o3 .若一个算法中的语句频度之和为T(n) = 3720n+4nlogn,则算法的时间复杂度为 o (a)

4、, b), c) ,(d)4 .广义表(由，9,。)，1)的表头是，表尾是o5.已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：将 累加。6 .要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s, 子链表最后一个结点的地址为t,则应执行操作： 和O7 .用带头结点的循环链表表示的队列，若只设尾指针rear,则队空的条件 是。8 .已知二维数组A10 20采用行序为主方式存储，每个元素占2个存储单元，并且 A00的存储地址是1024,则A618的地址是9.在表示二叉树的二义链表中，共有个空链域。10. n个顶点的连通无向图至少有条边，至多有条边。五、构造题：(每小题

5、6分，共30分)1 .已知二义树的中序序列为DBGEAFC,后序序列为DGEBFCA,给出对应的二叉树。2 .已知一个图的顶点为A、B、C、D,其邻接矩阵的上三角元素全为0 (包括主对角 线元素)，其他元素均为1。请画出该图，并给出其邻接表。3 .给定权值8, 12, 4, 5, 26, 16. 9,构造一棵带权路径长度最短的二叉树，并 计算其带权路径长度。4 .图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线 路花费的代价，请找出能连通每个城市、口总代价最省的n-l条线路。图25.对关键字序列(72, 87, 61, 23, 94, 16,05, 58)进行堆排序，使之

6、按关键字递减次序排列。请写出排序过程中得到的初始堆 和一趟排序后的序列状态。三、单项选择题：(每小题1分，共5分)2.在长度为n的顺序表的第i ( 1W i Wn+1 )个位置上插入一个元素，元素的移动 次数为：A) n-i+1B) n-iC) iD) i-l 3.下面关于图的存储的叙述中正确的是A)邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关；B.用邻接表 法存储图，占用的存储空间大小与图中边数和结点个数都有关C)邻接表占用的存储空间 只与图中结点个数有关，而与边数无关：D)邻接表占用的存储空间只号图中边数有关，而与结点个数无关。4.在待排序记 录已基本有序的前提下，下述排序方法

7、中效率最高的是：A)直接插入排序B)简单选择排序C)快速排序D)归并排序四、填空题:(每小题2分，共20分)1 .向一个有n个元素的有序表中插入一个新元素并保持原来顺序不变，平均要移动 n/2个元素。2 .设广义表L=(),(),则head(L)是 ；tail(L)是 ：L的长度是 ：深度是_head(L) = () tail(L) = (0)L的长度为2L的深度为2数据结构试卷A参考答案与评分标准(2001级)一、简答题：(每小题3分， 共15分)1.前驱与后继之间通常为一对多或多对多的关系。2.顺序表优点：随机查找，存 储密度大顺序表缺点：插入、删除不便，静态分配，表长固定单链表优点：插入

8、、删除方便, 动态分配，表长灵活单链表缺点：查找不便，存储密度小3.关键字相同的两个记录，排序前后其先后顺序不变。4. typedef struct node ElemType data; struct node * next; *LinkStack;5.当二又排序树接近平衡二叉树或完全二叉树时查找性能较好，当二义排序树为单 边单枝二又树时查找性能最差。三、单项选择题：(每小题1分，共5分)1. C) 2. C) 3. D) 4. B) 5. A)四、填空题：(每小题2分，共20分)1.12. ' YOU ARE RIGHT*5. i列元素>next=rear3. O(nlogn

9、)4.(a),b),c) >(d)6. t->next=p->next » p->next=s 7. rear-13009.n+110. n-1五、构造题：(每小题6分，共30分)1.3.或:WPL=8 X 3+4 X 4+5 X4+16X 2+9 X3+12X 3+26 X 2=207注:哈夫曼树的左右子树可以互换。4.解1：解 2：注:边上的权值可以省略。5.初始堆：05, 23, 16, 58, 94, 72, 61, 87一趟排序后的序列状态：87, 23, 16, 58, 94, 72, 61, 05筛成堆后为：16, 23, 61, 58, 94,

10、 72, 87, 05注:如果采用大根堆，应适当减分。六、算法设计题：(共25分)1.15分void min(LinkList L) if (L->next=NULL) return; q=L; r=L->next; m=r->data; while (l >next!=NULL) if(r->next->datar->next->data; q=r; r=r->next; p=q->next; if(m%2=l) q">next=p->next; free(p); 2.10 分void layer(CSTree root) InitQueue(&Q); EnterQueue(&