《数据结构与算法》期末练习题.doc

数据结构与算法期末练习 一 选择题1以下与数据的存储结构无关的术语是（ D ）。A循环队列 B. 链表 C. 哈希表 D. 栈2. 算法的时间复杂度取决于（ A ）A问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu3. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 24. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ） A（1），（2） B（1） C（1），（2）,(3) D.（2）5对于有n 个结点的二叉树, 其高度为（ D ）Anlog2n Blog2n Clog2n|+1 D不确定6从下列有关树的叙述中,选出正确的叙述（ C ）A二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B当K1时高度为K的二叉树至多有2k-1个结点。C哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。D在二叉树中插入结点,该二叉树便不再是二叉树。7设无向图的顶点个数为n，则该图最多有（ B ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En28已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, , , , , , , , ,G的拓扑序列是（ A ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V79下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 希尔排序，归并排序 D. 归并排序，冒泡排序10对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 84 11. 则采用的排序是 ( A )。 A. 选择 B. 冒泡 C. 快速 D. 插入12以下数据结构中，哪一个是线性结构（ D ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串13下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。14. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 415. 设n为正整数.下列程序段中前置以的语句的频度为（ B ）。i = 1; k = 0; do k+= 10*i; i+;While(i = n-1); A. n 1 B. n C. n + 1 D. n - 216. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）Alogn+1 Blogn+1 Clogn Dlogn-117一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=inext=null C. head=head D. head-next=head35. 在一个单链表中，已知*q是（*q表示指针q所指的结点，以下同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是( A )。 A) q-next=s; s-next =p B) s-next=p-next; q-next=s;C) p-nexr=s; s-next=p ; D) p-next=s; s-next=q;36. 非空循环链表head 的尾结点 *p 满足下列( C )条件A) head-next=p; B) head=p; C) p-next=head; D) p-next=037. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( D )。A. ecdab B) cebda C) daecb D) abcde38. 设栈s的类型为sqstack ，判定栈空的条件是( C )。A. s=NULL B) s-top=0 C) s.top=0 D) s.top=NULL 39. 深度为5 的二叉树至多有个( B )结点。A. 12 B. 31 C. 14 D. 1540. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二叉树的前根遍历序列是( C )。 A) defbca B) fedbca C) abcdef D) fedcba 41. 一个有n个顶点的有向图最多有( B )弧 。 A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/242. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连通图。A) n(n+1) B) n-1 C) n+1 D) n(n-1)43. 已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( B )。 A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 24 2 3 3 4 2 4 123444. 一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( C )A) 102 B) 110 C) 108 D) 12045. 一个循环顺序队列 ,队头、尾指针的值分别为front,rear ，则队列中元素个数为( A )。（maxlen为循环顺序表的长度）A. (rear-front+maxlen) % maxlen B. (rear-front) % maxlenC. rear-front+1 D. front-rear+146. 一个有n个顶点的图最少有( D )条边。A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 047. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连通图。A) 4 B) 5 C) 6 D) 748. 设栈s的类型为sqstack ，最多可容纳maxlen个元素，则判定栈满的条件是( B )。A. s=maxlen-1 B) s.top=maxlen-1 C) s-top=maxlen-1 D) s.top=049. 一个顺序队列q的类型为sqqueue,队头、尾指针分别为front,rear，最多可容纳maxlen个元素，则队空的条件是( C )。A) front=rear B) rear=0 C) q.front=q.rear D) rear=maxlen-150. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( B )A.O(1) B.O(n)C.O(nlogn) D.O(n*n)51. 链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况52. 二叉树中第5层上的结点个数最多为( C )A.8 B.15C.16 D.3253. 下列编码中属前缀码的是( A )A.1,01,000,001 B.1,01,011,010C.0,10,110,11 D.0,1,00,1154. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（B）A深度优先搜索算法B广度优先搜索算法C求最小生成树的prim算法D拓扑排序算法55. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( B )A.O(1) B.O(logn)C.O(n) D.O(n logn)56. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( C )A. (n-1)/2 B. n/2C. (n+1)/2 D. n57. 对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41 B.23和39C.15和44 D.25和5158. 关于线性表的说法,下面选项正确的是（ B ） A 线性表的特点是每个元素都有一个前驱和一个后继 B 线性表是具有n(n=0)个元素的一个有限序列 C 线性表就是顺序存储的表 D 线性表只能用顺序存储结构实现59. 表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（ A ） A (n-1)/2 B n/2 C n D n-160. 设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（ D ） A p-RLink=s; s-LLink=p; p-RLink-LLink=s; s-RLink=p-RLink; B p-RLink=s; p-RLink-LLink=s;s-LLink=p; s-RLink=p-RLink; C s-LLink=p; s-RLink=p-RLink; p-RLink=s; p-RLink-LLink=s; D s-LLink=p; s-RLink=p-RLink; p-RLink-LLink=s; p-RLink=s;61. 栈和队列都是（ A ） A 限制存取位置的线性结构 B 链式存储的非线性结构 C 顺序存储的线性结构 D 限制存取位置的非线性结构62. 单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（ A ） A O(n) B O(1) C O(n*n) D O(n*logn)63. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ） A n-k B n-k+1 C |logkn|+1 D |logkn| 其中|k|表示下取整 64. 下列序列中( B )不是堆。A. 12 36 53 68 48 60 75 B. 12 48 53 68 36 60 75C. 12 48 36 60 75 68 53 D. 12 36 60 53 48 68 7565. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。A. 直接插入排序 B. 简单选择排序C. 快速排序 D. 希尔排序66. 设顺序栈s非空，则语句段( C )可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem为栈空间，出栈的元素存放在x中。 A. s.top:=s.top+1; B. x:=s.elems.top; x:=s.elems.top; s.top:=s.top+1; C. s.top:=s.top-1; D. x:=s.elems.top; x:=s.elems.top; s.top:=s.top-1;67. 已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的后继结点应执行操作( A )；要在p结点后插入s结点应执行操作( D )。 A. pnext:=pnextnext; B. pnextnext:= .next; C. pnext:=s; snext:=pnext; D. snext:=pnext; pnext:=s;68. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。 A二叉排序树 B哈夫曼树 CAVL树 D堆69. 下面给出的四种排序法中( D )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 快速排序70. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序二 填空题1、在单链表L中，指针p所指结点有后继结点的条件是： p-next!=null2、表达式23+(12*3-2)/4+34*5/7)+108/9的后缀表达式是： (请在表达式中用点(.)将数隔开)23.12.3*2-4/34.5*7/+108.9/+3、有一个100*90的稀疏矩阵，非0元素有9个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 604、深度为9的完全二叉树具有的 个结点2565、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是 ABDEGCF6、先根遍历树林正好等同于按_ _遍历对应的二叉树.先序7、构造n个结点的强连通图，至少有_条弧。n8、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为 6,9,11,12 9、在单链表指针为p的结点之后插入指针为s的结点的操作是： s-next=p-next;p-next=s;10、有N个顶点的有向图，至少需要量_条弧才能保证是连通的。N-111、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值12，需做的关键码比较次数为 413、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处（顶点号由1开始） 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 该图的顶点数为 该图的边数为 顶点3的度为 。5 6 214、后根遍历树林正好等同于按_(6) _遍历对应的二叉树。中序15、n个结点的完全有向图含有边的数目_(7) n*（nl）16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的_。时间复杂度17、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为_。 SXSSXXSSXSSXXX18、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是_。219、如图所示的有向无环图可以排出_种不同的拓扑序列。1220、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(_ _)。75, 66, 48, 29, 31, 3721、对长度为20的有序表进行二分查找的判定树的高度为_。522、n个顶点的连通无向图，其边的条数至少为_。n-123、排序(sorting)有哪几种方法_，_，_，_，_。直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等24、下面程序段的时间复杂度为_。（用O估计） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j;O（n*n）25、非线性结构包括_和_。树，图26、在线性表的_存储结构上进行插入或删除操作要移动元素。顺序存储结构27、用一维数组r0. .m-1表示顺序存储的循环队列，设队头和队尾指针分别是front和rear，且队头指针所指的单元闲置，则队满的条件是_，队空的条件是_。Front=rear, rear+1=front28、下面表达式树所对应的表达式的前缀表达式是_，后缀表达式是_。+*a-bc/de , abc-*de/+29、在AOE-网中，设e(i)和l(i)分别表示活动的最早开始时间和最晚开始时间，则当且仅当_时，为关键活动。e(i)=l(i)30对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_。下面有向图的一个拓扑有序序列是_。存在回路，123456798 31、二叉排序树的特点是其 序列是有序的。 中序遍历三 简答题1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性；（3）散列法(hashing)；（4）索引文件。2、堆与二元查找树的区别?3、快速分类法的基本思想是什么?4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime 算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？12345657234154385、二叉树的后根遍历的序列中，任何一个非叶子结点均处在其孩子结点后面。该论断是否正确？ 6、有一棵哈夫曼树共有5 个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。7、对于一个队列，若入队的顺序为a,b,c, 则所有可能的出队序列是什么？8、已知一个图如下，试画出其逆邻接链表。 21349、若一个栈的输入序列是1,2,3，n, 其输出序列为p1,p2,pn,若 p1=n，则pi为多少？10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf ?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？ dabcef 13、栈的存储方式有哪两种？14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中：datenext单链表和单循环链表的结点结构为priordatenext双向链表的结点结构为 15、假设通信电文使用的字符集为a,b,c,d,e,f,g，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。16、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。17、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析。18、设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。19、 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。20、 试证明：若借助栈由输入序列1,2,n得到输出序列为P1,P2,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着ijk,使PjPkPi。四 算法阅读1、void AE(Stack& S) InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a5=1,5,8,12,15; for(i=0;ileft,c1,c2); c1+; if (BT-left=NULL&BT-right=NULL) c2+; ABC(BT-right,c1,c2); /if 该函数执行的功能是什么？3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）InitList(La); Int a=100,26,57,34,79; For (i=0;i5;i+) ListInsert(La,1,ai);（2）ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);（3）ClearList(La); For (i=0;i5;i+) ListInsert(La,i+1,ai);4、int Prime(int n) int i=1; int x=(int) sqrt(n); while (+ix) return 1; else return 0; (1)指出该算法的功能；(2)该算法的时间复杂度是多少？5. 写出下述算法A的功能： 其中BiTree定义如下: Typedef struct BiTNode TElemType data; struct BiTNode *LChild, *RChild;BiTNode, *BiTree;Status A(BiTree T) Queue Q; InitQueue(Q); ENQueue(Q,T); While(not QueueEmpty(Q) DeQueue(Q,e); If(e=NULL) break; Else Print(e.data);ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); 6.阅读下列函数algo,并回答问题：(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；(2)简述算法algo的功能。void algo(Queue *Q) Stack S; InitStack(&S); while (!QueueEmpty(Q) Push(&S, DeQueue(Q); while (! StackEmpty(&S) nQueue(Q,Pop(&S);五 算法填空1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。typedef struct node int data; struct node *next; lklist;void del( lklist rear, int &x); lklist p,q; q=rear- next; if (_) printf( “it is empty!n” ); else p=q-next; x=p-data; _ ; if (_) rear=q; ; ;2、堆分配存储方式下，串连接函数。typedef struct char * ch； int len； HString； HString *s， t; Status StrCat(s， t) /* 将串t连接在串s的后面 */ int i; char *temp; f if (temp=NULL) return(0); for (i=0; ;i+) tempi=s-chi; for ( ;ilen + t.len;i+) tempi=t.chi-s-len; s-len+=t.len; fr s-ch=temp; return(1); 3、向单链表的末尾添加一个元素的算法。 LNode是一个包含（data，Next）的结构体Void InsertRear(LNode*& HL,const ElemType& item)LNode* newptr;newptr=new LNode;If (_)cerrMemory allocation failare!next=NULL;if (HL=NULL) HL=_;elseLNode* P=HL;While (P-next!=NULL) _;p-next=newptr; 4、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。LinkList f30(LinkList L, int c) LinkList Lc,p,pre; pre=L; p= (1) ; Lc=(LinkList) malloc(sizeof(ListNode); Lc-next=Lc; while(p!=L) if(p-datac) pre-next=p-next; (2) ; Lc-next=p; p=pre-next; else pre=p; (3) ; return Lc; vertexfirstedge5、已知图的邻接链表的顶点表结点结构为 adjvexnext边表结点EdgeNode的结构为下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。int FindDegree(ALGraph *G,int i)/ALGraph为图的邻接表类型 int dgree, j; EdgeNode *p; degree= (1) ; for(j=0;jn;j+) p=G-adjlistj. firstedge; while ( (2) ) if( (3) ) degree+; break; p=p-next; return degree;六 简单应用题1、已知一个非空二元树，其按中根和后根遍历的结果分别为：中根：C G B A H E D J F I后根：G B C H E J I F D A试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么?2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。3、画出由下面的二叉树转换成的森林。4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表： A A(0) A(1) A(2) A(3) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3PATH PATH(0) PATH(1) PATH(2) PATH(3) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 35、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。weightParentLchildRchildweightParentLchildRchild123456789101112131415500029000700080001400023000300011000-000-000-000-000-000-000-0001234567891011121314156、考虑右图：(1)从顶点A出发，求它的深度优先生成树(4分)(2)从顶点E出发，求它的广度优先生成树(4分)(3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程)(设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分)答案如下：七 编写算法题1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data 域中。void count1(lklist head,int x)2、设计递归函数，求一棵二叉树的深度。int depth (bitreptr root)3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。 Typedef struct int data maxsizemaxsize; int dem,e;sqgraph; sqgraph crt (sqgraph g) 4、设计函数，将不带表头结点的单链表清除。5、设计递归函数，求一棵非空的二叉树的深度。6、设线性表A=(a1,a2,a3,