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