数据结构期末复习题1

数据结构习题1一、选择题1、程序段如下：sum=0；for(i=1;i<=n;i++)for(j=n;j>=1;j--)sum++；其中n为正整数，则最后一行的语句频度在最坏情况下是（）。A、O(n）B、O(nlog2n)C、O(n3)D、O(n2)2、二维数组A[8][8]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][5]的存储地址为1159，则数组元素A[6][7]的存储地址为（）。A、1223 B、1227C、1231 D、12353已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不会出现的出栈序列为（）。A、4，3，2，1，5，6 B、3，2，1，6，4，5C、4，3，2，1，6，5 D、3，2，1，6，5，4已知广义表C=(a，(b，c)，d)，则：head(tail(tail(C)))为()A、d B、cC、b D、a已知一棵完全二叉树有256个叶子结点，则该树可能达到的最大深度为（）。A．10 B．11C．8 D．96、已知森林F={T1，T2，T3，T4，T5，T6}，各棵树Ti(i=1，2，3，4，5，6)中所含结点的个数分别为18，2，3，4，5，6,将F按照左孩子右兄弟转化为二叉树，则与F对应的二叉树的右子树的结点个数为（）。A．19 B．20C．17 D．187、对下图所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问序列（）。A.1245637 B.1243567C.1243576 D.12345768.下列关键字序列中，（）是堆。Ａ.16,72,31,23,94,53Ｂ.94,23,31,72,16,53Ｃ.16,53,23,94,31,72Ｄ.16,23,53,31,94,729、对记录序列(314，508，298，123，486，145)依次按个位进行一趟基数排序之后所得的结果为()。A、 298，123，508，486,145，314B、508，314，123，145，486，298C、123，314，145，486，298，508 D、123，314，145，486，508，29810、已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（）。A、(18,22,30,46,51,75,68,83) B、(30,22,18,46,51,75,83,68)C、(30,22,18,46,51,75,68,83) D、(30,22,18,46,51,83,68,75)二、填空题1、使用一个30个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=29，rear=0，则队列中的元素个数为___________。2、一棵二叉树有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树共有____个结点；若某棵完全二叉树共有100个结点，则该叶子结点数为。3、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到的线性序列为。 4、在有序表（22，34，46，58，70，82，94）中二分查找关键字22时所需进行的关键字比较次数为。5、将整数序列{40,50,70,20,10,30}中的数依次插入到一棵空的平衡二叉树中，画出相应的平衡二叉树。三、应用题1、已知字符串‘abaabababc’，采用KMP算法，计算每个字符的next和nextval函数的值。2、假设某系统在通信联络中只可能出现5个字符(a,b,c,d,e)，其概率分别为：0.15，0.30，0.20，0.28，0.07，画出构造的Huffman树和Huffman编码。3、设带权有向图如下所示：求出源点V1到汇点V9之间的关键路径。4、已知Hash函数为H（K）=Kmod9，哈希表长为9，用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49,52）在散列表中的分布，并求在等概率情况下查找成功的平均查找长度。5、已知3阶B-树如右图所示，画出将关键字18、110和120依次插入之后的B-树。四、程序阅读题1、设有单链表类型定义如下：voidf41(LinkListhead,intA,intB){LinkListp=head;while(p!=NULL){if(p->data=>A&&p->data<=B)printf("%d\n",p->data);p=p->next;}}已知链表h如下图所示，给出执行f41(h，4，8)之后的输出结果；∧1h69785∧1h697852、写出下面程序运行之后的结果。voidf42(intn)//n为非负的十进制整数{inte;SeqStackS;InitStack(&S);//堆栈初始化do{Push(&S,n%2);//入栈n=n/2;}while(n);while(!StackEmpty(&S))//如果堆栈不空，循环{e=Pop(&S);//出栈printf("%ld〞,e);}}main(){

f42(100);}3、假设以二叉链表作为二叉树的存储结构，其类型定义如下：typedefstructnode{chardata;structnode*lchild,*rchild;／／左右孩子指针}BinTNode,*BinTree；已知如图所示的二叉树以T为指向根结点的指针，画出执行f43(T)后的二叉树；voidf43(BinTreeT){BinTreetemp;if(T){f43(T->lchild);if((T->lchild)&&T->rchild){temp=T->lchild->data;T->lchild=T->rchild;T->rchild=temp;}f43(T->rchild);}}4、下面程序实现二分查找算法。Typedefstruct{KeyTypekey；InfoTypeotherinfo；}SeqList[N+1]；intBinSearch(SeqListR,intn，KeyTypeK){intlow=1，high=n；while((1)){mid=(1ow+high)／2；if((2))returnmid；if(R[mid]．key>K)high=mid-1；else(3)；}returnO；}／／BinSearch请在空白处填写适当内容，使该程序功能完整。五、编程题（每题10分，共20分）1、已给一个带表头结点的单链表head，结点元素值按升序排列，