1、 所有试卷资料免费下载 第 1 页 共 9 页 西安电子科技大学 数据结构复习题 （含部分参考答案版） 一、 单项选择题 1. 按照数据逻辑结构的不同，可以将数据结构分成 C 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 2. 下列关于数据结构的叙述中正确的是 A 。 A. 数组是同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为复杂 C. 树是一种线性的数据结构 D. 用一维数组存储二叉树，总是以先序顺序遍历各结点 3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为 B A.逻辑结构 B.
2、顺序存储结构 C.链式存储结构 D.以上都不对 4. 以下关于算法特性的描述中， B 是正确的。 （1）算法至少有一个输入和一个输出 （2）算法至少有一个输出但是可以没有输入 （3）算法可以永远运行下去 A. （1） B. （2） C. （3） D. （2）和（3） 5. 对顺序存储的线性表（a 1,a2,an）进行插入操作的时间复杂度是 C 。 A.O(n) B. O(n-i) C. (n/2) D. O(n-1) 6. 链表不具有的特点是 A 。 A.可随机访问任一元素 B.插入和删除时不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表的长度成正比 7.线性链表中各链结点之间的
3、地址 C 。 A.必须连续 B.部分地址必须连续 所有试卷资料免费下载 第 2 页 共 9 页 C.不一定连续 D.连续与否无关 8. 以下关于链式存储结构的叙述中， C 是不正确的。 A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第 i 个结点的存储地址 D.插入、删除操作方便，不必移动结点 9. 设依次进入一个栈的元素序列为 d, a, c, b,得不到出栈的元素序列为 D 。 A. dcba B. acdb C. abcd D. cbda 10. 将新元素插入到链式队列中时，新元素只能插入到 B 。 A. 链头
4、 B. 链尾 C. 链中 D. 第 i 个位置，i 大于等于 1，大于等于表长加 1 11. 设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 S，一 个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2、e4、e3 、e6、e5、和 e1， 则栈 S 容量至少应该是 C 。 A. 6 B. 4 C. 3 D. 2 12.下面 D 是abcd321ABCD 的子串。 A. abcd B. 321ab C. abc ABC D. 21AB 13.假设 8 行 10 列的二维数组 A18，110分别以行序为主序和以列序为主序顺序存 储时，其首地
5、址相同，那么以行序为主序时元素 a3，5的地址与以列序为主序时 C 元素相同。 A. a7，3 B. a8，3 C. a1，4 D. ABC 都不对 14. 数组 A05，06的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A5，5的地址为 A 。 A. 1175 B. 1180 C. 1205 D.1210 15.下列广义表中，长度为 3 的广义表为 B 。 A.（a,b,c,( )） B. (g),(a,b,c,d,f),( ) C. (a,(b,(d) D. ( ) 16. 以下关于广义表的叙述中，正确的是 A 。 A. 广义表是 0 个或多个
6、单元素或子表组成的有限序列 B. 广义表至少有一个元素是子表 所有试卷资料免费下载 第 3 页 共 9 页 C. 广义表不可以是自身的子表 D. 广义表不能为空表 17.若树 T 有 a 个度为 1 的结点，b 个度为 2 的结点，c 个度为 3 的结点，则该树有 D 个叶结点。 A. 1+2b+3c B. a+2b+3c C.2b+3c D. 1+b+2c 18.若一棵二叉树有 102 片叶子结点，则度二叉树度为 2 的结点数是 B 。 A. 100 B. 101 C. 102 D. 103 19. 在有 n 个叶子结点的霍夫曼树中，其结点总数为： 。 A. n B. 2n C. 2n +1
7、 D. 2n - 1 20.具有 12 个结点的完全二叉树有 B 。 A. 5 个叶子结点 B. 5 个度为 2 的结点 C. 7 个分支结点 D. 2 个度为 1 的结点 21.设结点 x 和 y 是二叉树中的任意两结点，若在先根序列中 x 在 y 之前，而后根序列中 x 在 y 之后，则 x 和 y 的关系是 C 。 A. x 是 y 的左兄弟 B. x 是 y 的右兄弟 C. x 是 y 的祖先 D. x 是 y 的后代 22. 先序遍历序列与中序遍历序列相同的二叉树为 。 A. 根结点无左子树的二叉树 B.根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
8、D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树 23.若二叉树 T 的前序遍历序列和中序遍历序列分别是 bdcaef 和 cdeabf，则其后序遍历序 列为 A 。 A. ceadfb B. feacdb C. eacdfb D. 以上都不对 24.设无向图的顶点个数为 n，则该图最多有 C 条边。 A. n-1 B. n(n-1) C. n(n-1)/2 D. n 25.对于一个有 n 个顶点和 e 条边的无向图，若采用邻接表表示，邻接表中的结点总数是 C 。 A. e/2 B. e C. n+2e D. n+e 所有试卷资料免费下载 第 4 页 共 9 页 26. 无向图 G=（V
9、，E） ，其中 V=a,b,c,d,e,f ,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 。 对该图进行深度优先遍历，下面不能得到的序列是 D 。 A. acfdeb B. aebdfc C. aedfcb D. abecdf 27.在下述排序方法中，不属于内排序方法的是 C 。 A. 插入排序法 B. 选择排序法 C. 拓扑排序法 D. 归并排序法 28. 直接插入排序在最好情况下的时间复杂度为 B 。 A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 29.对有 n 个记录的表作快速排序，在最坏情况，算法的时间复
10、杂度是 D 。 A. O(n3) B. O(n) C. O(nlog2n) D. O(n2) 30.下面的排序算法中，稳定是 A 。 A. 直接插入排序法 B. 快速排序法 C. 直接选择排序法 D. 堆排序法 二、 填空题 1. 一个算法具有 5 个特性： 、 、 、有零个或多个输入， 一个或多个输出。 2. .设数组 a150，180的基地址为 2000，每个元素占 2 个存储单元，若以行序为主 序顺序存储，则元素 a45，68 的存储地址为 9174 ；若以列序为主序顺序存储， 则元素 a45，68的存储地址为 8788 。 3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但
11、要求以最快的速度存 取线性表中的元素时，应采用 存储结构。 4.两个字符串相等的充分必要条件是 长度相等且对应位置上的字符相等 。 5. 字符串“abcd”中共有 个长度大于 0 的字串。 6. 广义表 list=（5， （3，2， （14，9，3） ， （） ，4） ，2， （6，3，10） ）的长度及深度分别 为 和 。 7.若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点 。 8.若无向图满足 有 n-1 条边的连通图 ，则该图是树。 9.若无向图中有 n 个顶点，则其边数最少为 n-1 ，最多为 n(n-1)/2 。 10.堆排序的时间复杂度和空间复杂度分别为 O(
12、nlog2n) 和 O(1) 。 所有试卷资料免费下载 第 5 页 共 9 页 三、 名词解释 （1）抽象数据类型 （2）算法及其特性 （3）串的模式匹配 （4）优先级队列 （5）完全二叉树 （6）堆（7）Huffman 编码（8）Huffman 树 （9）连通分量及重连通分量（10）最小生成树（11）克鲁斯卡尔算法 （12）普里姆算法（13）希尔排序（14）快速排序 （15）教材等等相关名次解释题 四、 简答题 1. 请对线性表进行顺序存储和链式存储的特点作比较。 （西电 2004 年考研试题） 2. 单链表为什么要引入头结点？ 3.线性表的链式存储结构有单链表、循环链表、双向链表，试问它们
13、各有什么优点和缺 点？ 参考答案： 单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是 不能随机访问数据。和其它两种相比，它还节省了空间。 循环链表除了具有单链表的优点外，它从任意结点出发可以找到其它结 点。缺点同单链表的缺点。 双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前 驱。缺点是增加了空间开销。 4.内存中一片连续空间（不妨假设地址从 1 到 m） ，提供给两个栈使用，怎样分配这部分 存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 5. 假设有一个适当大小的栈 S，输入栈的序列为 A，B，C，D ，E。 问：（1）能否得到下列的输出序列： B，C
14、，D，E，A； E，A，B，C，D； E，D，C，B，A。 （2）写出所有可能正确的输出序列（至少 5 种） 。 6.用向量表示的循环队列的队首和队尾位置分别为 1 和 max_size，试给出判断队列为空 和为满的边界条件。 参考答案： 队空条件为 max_size=1; 队满的条件为（max_size+1）%MAXSIZE. 7. 设一棵二叉树后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，要求： （1）画出该二叉树； （2）写出该二叉树的先序遍历序列； （3）画出该二叉树对应的森林。 所有试卷资料免费下载 第 6 页 共 9 页 8.对二叉树中的结点按层次顺序
15、（每一层自左向右）进行的访问操作称为二叉树的层次 遍历。现已知一棵二叉树的层次序列为 AEBGFDIMH，中序遍历序列为 GEFAMDBHI。请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的 孩子 兄弟表示，请画出该森林。 （西电 2004 年考研试题） 9. 已知某通信电文仅由 A、B、C、D、E、F 这 6 个字符构成，其出现的频率分别为 23、5、14、8、25、7，请给出它们的霍夫曼树及其对应的霍夫曼编码。 10.给定下列图 G 用两种不同表示法画出该图的存储结构图。 A B GFE D C 4 8 12 2 4 20 12 15 10 11. 针对上图分别用卡鲁斯卡尔及普
16、里姆算法给出该图的最小生成树，画出其逻辑结构。 12.总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、 锦标赛排序、堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅 助空间复杂度及稳定性。 13.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。 （1）100，90，80，60，85，75，20，25，10，70，65，50 （2）100，70，50，20，90，75，60，25，10，85，65，80 14.已知一序列（12，70，33，65，24，56，48，92，86，33） ，问该序列是否是堆？如 果不是，则把它调整为小顶堆。并
17、问把该序列调整为堆共需要多少次元素间的比较？ 多少次元素间的交换。 （西电 2005 年考研试题） 15.试为下列情况选择合适的排序算法：（西电 2006 年考研试题） （1）n=30，且要求最坏情况下速度最快； （2）n=30，且要求既要快，又要排序稳定； （3）n=2000 ，要求平均情况下速度最快； 所有试卷资料免费下载 第 7 页 共 9 页 （4）n=2000 ，要求最坏情况下速度最快，又要节省存储空间。 五、 算法设计题 1. 实现一个算法，完成在不带表头结点的单链表第 i 个结点之前插入新元素 x 的操作。 （教材 P74 页） 2.（a）实现一个函数，完成在带表头结点的双向循环
18、链表中，建立一个包含有值 value 的新结点并将其插入到当前结点之后。 （教材 P91 页） （b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让当前 指针指到链表中下一个结点位置。 （教材 P91 页） 3.（a）实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。 （教材 P107 页） （b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。 （教材 P117 页） 4.对二叉链表，实现一个函数 Parent(*BinTreeNode*start, *BinTreeNode*curent)从结点 start 开始，搜索结点 current 的双亲结点
19、，并返 回其地址，否则返回 NULL。 （教材 P171 页） 5. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法： （1）统计二叉树中叶子结点的个数； （2）交换每个结点的左子女和右子女。 6.熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序 的算法 7.若以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和队列中元素的个数。 请完成下面的入队列和出队列的算法：（西电 2004 年考研试题） #define MAXQSIZE 100 /最大队列长度 Type struct Qelemtype *base; /base 为队列所在区
20、域的首地址 int length; /队列长度 int rear; /队尾元素位置 SqQueue; Status EnQueue(SqQueue / 队列满，无法插入 Q.rear= ; /计算元素 e 的插入位置 所有试卷资料免费下载 第 8 页 共 9 页 = e; /在队尾加入新的元素 Q.length+; /队列长度加 1 return OK; Status DeQueue(SqQueue /队列满 e=Q.base ; /取队头元素 Qlength -; /队列长度减 1 return OK; 8.请运用快速排序思想，设计递归算法实现求 n（n1）个不同元素集合中的第 i（1in）
21、小元素。 （西电 2004 年考研试题） 9.阅读下列函数说明及相应代码，在空白处填入相应语句。 (西电 2005 年考研试题) 函数 1 函数 palinddrome(char s)的功能是：判断字符串 s 是否为回文字符串，若是，则返回 0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如： “LEVEL”是回文字符串，而“LEVAL ”不是。 Int palindrome (char s) char *pi, *pj; Pi = s; pj =s + strlen(s) 1; /*strlen(s)函数用于求得串 s 的串长 While（pipj pi - -
22、; if ( )return - 1; else return 0; 函数 2 函数 insert_sort(int a,int count)是用直接插入排序法对指定数组的前 count 个元素从 所有试卷资料免费下载 第 9 页 共 9 页 小到大排序。 Void insert_sort(int a, int count) int i, j, t; for (i=1;icount;i+)/控制 ai，acount-1的比较和插入 t = ai; j= ; while (j0 j - -; ; 10. 假设以数组 seq0m-1存放循环队列中的元素，同时设变量 rear 和 quelen 分别指示 循环队列中的队尾元素的位置和内含元素的个数。(西电 2006 年考研试题) 请给出： （1）给出循环队列的队满条件和队空条件； （2）写出相应的入队列和出队列的算法，并分别分析其时间代价； （3）如果用数组 sequmn来存放循环队列中的元素，则（ 2）中的入队列和出队列的 算法中的哪些语句要修改？如何修改？
