数据结构试题A.doc

数据结构试题（A） 姓名_ 学号_ 班级_ 分数_一、 选择填空（每空1分，共20分）1 _是数据的不可分割的最小单位。 (A) 结点 (B) 数据元素 (C) 数据类型 (D) 数据项2 若线性表最常用的操作是存取第i个元素及其前趋的值，则采用_存储方 式节省时间。 (A)单链表 (B)双向链表 (C)单循环链表 (D)顺序表 3 对长度为14的表作2路归并，共需移动_次记录。 (A)42 (B)56 (C)91 (D)182 4 n个顶点的无向图的的邻接表中结点总数最多有_个。 (A) 2n (B) n (C) n/2 (D) n(n-1) 5 设连通图G的顶点数为n，则G的生成树的边数为_。 (A) n-1 (B) n (C) 2n (D) 2n-1 6 在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立图的 算法的时间复杂度为_。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3) 7 使用监视哨，对表（25，20，10，42，28）作直接插入排序，共需比较_次。 (A)10 (B)6 (C)8 (D) 答案A，B，C都不对8 以知一棵二叉树的前序和中序序列分别为ABDEGCFH 和DBGEACHF 则该二叉树 的后序序列为 _。(A) GEDHFBCA (B) DGEBHFCA (C) ABCDEFGH (D) ACBFEDHG 9 深度为K的满二叉树有_个叶结点。 (A)K2-1 (B)2K-1-1 (C)2K-1 (D)2K-1 10下列算法中，某一轮结束后未必能选出一个元素放在其最终位置上 的是_。 (A)堆排序 (B)冒泡排序 (C)直接插入排序 (D)快速排序 11 将新元素插入到链式队列中时，新元素只能插入到_。 A 链头 B 链尾 C 链中 D 第i 个位置 （i=1且i=0)个 _的有限序列。 A 字符 B 表元素 C 数据元素 D 数据项15 从逻辑上，可以将数据结构分为_两类。 A 动态表和静态表 B 顺序结构和链式结构 C 线性结构和非线性结构 D 动态结构和静态结构16 设无向图的顶点个数为n，则该图最多有_条边。 A n-1 B n(n-1)/2 C n(n+1)/2 D n17 有8个叶子结点的二叉树有_个度为2的结点。 A 7 B 16 C 64 D 9 18 深度为5的满二叉树有_个结点。 A 32 B 15 C 31 D 16 19 二分查找有序表（16，20，30，35，40，46，60，78），若查找元素 78，需依次与表中的 _进行比较。 A 40，60 B 35，46，60，78 C 40，60，78 D 35，46，7820 算法应具的特点不包括_。 A 确定性 B 可行性 C 一一对应性 D有输入、输出 二 问题求解（每小题6分，共30分）1 给定下列网络G： 1）求最小生成树，画出逻辑图；2）画出G的邻接矩阵和邻接表。ABCEF22049682 依次输入元素：10，6，8，3，42，25，7，30，27，60试生成一棵二叉排序树， （1）画出生成之后的二叉排序树；（2）写出中序遍历该二叉排序树的序列；（3）假定每个元素的查找概率相等，计算查找成功时的平均查找长度。 3 如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都 集中到对角线以上？试举一例加以说明。4 找出所有二叉树，其结点在下述两种次序之下，恰好都以同样的顺序出现： a) 前序和中序；b) 前序和后序 5 对下列关键字序列用快速排序法排序，哪一种情况速度最快？哪一种 情况速度最慢？为什麽？ A（19，23，3，15，7，21，28） B（ 23，21，28，15，19，3，7） C （3，7，15，19，21，23，28）三 简述下述算法的功能（每小题6分，共18分）1 写出以下程序段的输出结果。void main () queue q ; char x = e ; char y = c ;initqueue (q) ; / 构造一个空队列qenqueue (q, h ) ; / 将元素h到队 q的尾部enqueue (q, r ) ;enqueue (q, y ) ;dequeue (q, x ) ; / 删除队q的队首元素xenqueue (q, x ) ;dequeue (q, x ) ;enqueue (q, a ) ;while ( !queueempty (q) ) / 当队q非空 dequeue(q, y) ; printf (y) ; printf (x) ; 2 简述以下算法的功能。 (1) void a3 (queue &q) stack s ; int d ; initstack (s) ; / 构造一个空栈s while (!queueempty (q) / 当队q非空时 dequeue(q, d) ; / 从队q删除一个元素保存在 d中 push (s, d) ; / 将d中的元素插入到栈 s里 while (!stackempty (s) / 当栈s非空 pop (s, d) ; / 弹出栈s的顶元保存在 d中 enqueue (q, d) ; / 将d插入到队 q的尾部 (2) void change ( linklist &head ) /head是无表头结点的单链表 linklist q ,p ; if (head & head-next) q=head ; head=head-hext; p=head ; while (p-next) p=p-next ; p-next=q ; q-next=NULL ; 四、算法设计（每题16分，共32分）1 编写一个算法交换单链表中p所指位置上和其后继位置上的两个结点，head为头指针，设该链表没有表头结点，p指向该链表中任意结点。结点的结构如下： typedef struct node elementype data ; struct node *next ; node ; 2 已知线性表中的元素以递增的顺序排列并以向量作存储结构，试编写一高效算法删除表中所有值大于mink且小于maxk的元素（注意:mink可和maxk是给定的两个参数，它们的值可以和表中的元素相同，也可以不同）。假设向量中的元素分别为（1，2，3，4，5，6，7，8，9，10 ），欲删除值大于等于3而小于等于7的元素，请统计算法中元素的移动数。 参 考 答 案一 选择填空 1D 2D 3B 4D 5A 6A 7C 8B 9D 10C11B 12C 13D 14C 15C 16B 17A 18C 19B 20C二 问题求解 1064287272530603ABCEF204621 2A B C E FA 0 2 0 4 0 中序序列：3，6，7，8，10，25，27，30，42，60B 2 0 20 8 9 平均查找长度： 3 C 0 20 0 0 0E 4 8 0 0 6F 0 9 0 6 0 ABCEF1 2 3 4 5 T=0110010001211133 使得有向图中每条边始顶点的编号小于终顶点的编号。4 前序和中序 空树和具有所有的左链为空的二叉树。前序和后序 具有0个或1个结点的二叉树。5 A（19，23，3，15，7，21，28）-最快，2轮 B（ 23，21，28，15，19，3，7） C （3，7，15，19，21，23，28）-最慢，7轮 最快的情况是每次将第一个元素放到正确位置后，将整个文件分为两个 等长的子表，其时间复杂度为对数阶，最慢的情况是每次只能得到左 子表或右子表其时间复杂度为平方阶。三 简述下述算法的功能1 输出结果是 char2 算法的功能是：利用栈s作辅助结构，将队列q 中的元素进行逆置。3 当单链表的长度大于等于2时，删除表中第一个 结点并将它插入到表尾。四、1 如果p存在后继结点，则看它是否是第一个结点。如果是，则交换后须改变该链表的头指针head 的值，否则直接交换即可。 void swap(linklist &head, linklist p) linklist q, r, s ; q = p -next ; if ( q != NULL)/ 若p存在后继，则进行处理 if ( p = head ) /若p指向第一个结点，则前两个结点交换位置 head = head-next ; s = head-next ; head-next = p ; p-hext = s ; else / 若p指向第二个或第二个以后的结点 r = head ; / 从第一个结点开始查找p的直接前趋结点 while ( r-next != p ) r = r-next ; r-next = q ; / 交换p,q结点的顺序 p-next = q-next ; q-next = p; printf( succ); else printf( NULL); / p所指结点没有后继 2 本算法的思想是从表的第一个元素开始依次向后扫描，找到第一个值大于等于mink的元素和第一个小于等于maxk 的元素 则分别记下它们位置，然后一次性删除这些元素。此方法元素移动量最小。int del_3(int a , int mink, maxk, n ) int i, m, j, k ; i = 0; while ( i =n-1