数据结构(第二版)期末考试卷4套及答案.doc

试卷一一、选择题（本题共30分,每题2分）1. 计算机识别、存储和加工处理的对象被统称为_。A. 数据 B. 数据元素 C. 数据结构 D. 数据类型2. 已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列_。A1234B4321 C2143D41233. 链表不具有的特点是_。A. 随机访问 B. 不必事先估计所需存储空间大小C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比4. 设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是_InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x)A. a B. b C.NULL D.x5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_。Ap=q-next; p-next=q-next;free(p);Bp=q-next; q-next=p; free(p);Cp=q-next; q-next=p-next; free(p);Dq-next=q-next-next; q-next=q; free(p);6. 一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是_。A110 B108 C100 D1207. 在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是_。A. n-i B. n-i+1 C. n-i-1 D. i8下面关于线性表的叙述错误的是_。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现9. Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是_。A.Push(A) Push(B) Pop(A) Pop(B)B.Push(A) Push(B) Pop(B) Pop(A)C.Push(A) Pop(B) Push(B) Pop(A) D.Push(B) Pop(A) Push(A) Pop(B)10.下列查找方法中哪一种不适合元素的链式存储结构_。A顺序查找 B分块查找 C二分查找 D散列查找11. 下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是_。A. 快速排序 B.希尔排序 C.堆排序 D.冒泡排序12. 设一棵二叉树的深度为k，则该二叉树中最多有_个结点。 A 2k-1B. 2kC. 2k-1D. 2k-113. 下列四个选项中，能构成堆的是_。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20, 15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边_。An(n-1)/2 Bn-1 Cn Dn+115.栈和队列的共同特点是_。A. 都是操作受限的线性表 B.都是先进后出 C. 都是后进先出 D.无共同点二、填空题（本题共 10分，每空1分）1. 若经常需要对线性表进行查找操作，则最好采用_存储结构。2. 某带头结点单链表的头指针为L，判定该单链表非空的条件_。3. 数据的逻辑结构包括集合、_、_和图状结构四种类型。4. 图的两种遍历方式为：广度优先遍历和_。5. 线性表的链式存储结构中的结点包含_域和_域。6. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_上。7. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedef struct int stack100; int top; seqstack;void push(seqstack *s,int x)if (s-top=99) printf(“overflow”);else _(1)_;_(2)_;三、应用题（本题共40分） 1 设散列表长度为11，散列函数h(key)=key % 11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查找成功时候的平均查找长度。（6分）2有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）3已知图G=(V,E)，其中V=1,2,3,4,5, E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)。要求完成如下操作：（6分）（1）写出图的邻接矩阵（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。4已知序列503，87，512，61，908，170，897，275，653，462，分别写出执行下列排序算法的各趟排序结束时，关键字序列的状态：（10分）（1）直接插入排序（2）基数排序5对于下面所示的连通图，写出由Prim算法生成的最小生成树。（5分） 6. 将下面的树转化为一棵二叉树,并写出对二叉树进行层序遍历的序列。（7分）ABCDEFGH四、算法题（本题共20 分）1完成中序遍历二叉树。Typedef struct node Char data; Struct node *lchild;Struct node *rchild;BTreeNode,*LinkBtree; Void InOrder(LinkBtree Bt_pointer) If(Bt_pointer!=NULL) _(1)_; _(2)_; _(3)_; 2.完成二分查找算法：#Define n 10typedef int KeyType;typedef struct KeyType key; NodeType;Typedef NodeType SeqListn+1;int BinSearch (SeqList R,KeyType k)int low=1,high=n,mid;while(_（4）_) mid=(low+high)/2; if(Rmid.key=k) return mid; if(Rmid.keyk) _（5）_; else _（6）_;return 0;3.编写算法实现直接插入排序。（8分） 参考答案一、选择题（本题共30分,每题2分）123456789101112131415ADABCBBDACBDCBA二、填空题（本题共10分，每空1分）1） 顺序 2）L-next!=NULL3） 线性结构 树形结构 4） 深度优先遍历5） 数据 指针 6）左子树7） s-top+ s-stacks-top=x 三、应用题（本题共40分）1、（6分）H(1)=1 H(13)=2 H(12)=1 冲突 ， H1=2 冲突， H2=3 H(34)=1 冲突 ， H1=2 冲突， H2=3 冲突， H3=4 H(38)=5 H(33)=0 H(2)=2 冲突 ， H1=3 冲突， H2=4 冲突， H3=5 冲突， H4=6 H(22)=0 冲突 ， H1=1 冲突， H2=2 冲突， H3=3 冲突， H4=4 冲突，H5=5 冲突， H6=6 冲突， H7=7 ASL=(1+1+3+4+1+1+5+8)/8=24/8=3 2、（6分）1104961212829321415Wpl=2493、图的邻接矩阵：（3分） 广度优先序列： 1 2 3 4 5（3分）0 1 1 1 01 0 1 0 11 1 0 1 01 0 1 0 10 1 0 1 0 4、 1）（503）87 512 61 908 170 897 275 653 462（5分） （87 503）512 61 908 170 897 275 653 462 （87 503 512）61 908 170 897 275 653 462（61 87 503 512）908 170 897 275 653 462（61 87 503 512 908）170 897 275 653 462（61 87 170 503 512 908）897 275 653 462（61 87 170 503 512 897 908）275 653 462（61 87 170 275 503 512 897 908）653 462（61 87 170 275 503 512 653 897 908）462（61 87 170 275 462 503 512 653 897 908） 2）第一趟： 170 61 512 462 503 653 275 87 897 908（5分） 第二趟： 503 908 512 653 61 462 170 275 87 897 第三趟： 61 87 170 275 462 503 512 653 897 9085、（5分） ABDEFGHC6. （7分）层序遍历序列:ABECFDGH四、算法题（本题共20分）1、 （1）InOrder (Bt_pointer -lchild); （2分） (2) printf(“%c”, Bt_pointer -data);（2分） (3) InOrder (Bt_pointer -rchild); （2分）2、 （4） low=high （5）high=mid-1; （6） low= mid+1; （6分）3、 void InsertSort(int a,int n) （8分） int i,j; for(i=2;i=n;i+) a0=ai; j=i-1; while(a0aj) aj+1=aj; j-; aj+1=a0;试卷二一、选择题（本题共20分,每题2分）1.下面程序段的时间复杂度为（ ）。for(i=1;i=n;i+) for(j=1;j=n;j+) s+;A. O(n) B. O(n2) C. O(2*n) D. O（i*j）2. 线性表采用链式存储时，结点的存储地址（ ）。A必须是不连续的 B部分地址必须是连续的C连续与否均可 D和头结点的存储地址相连续3.若让元素1，2，3依次进栈，则出栈时的序列不可能出现的是（ ）。 A3，2，1 B1，2，3 C3，1，2 D2，1，34.下面说法不正确的是()A串S1=“this_is_a_string”的长度是16。 B串S2=“this”是串S1的子串。C串S3=“thisis”在串S1中的位置是1。D串S4=“a”在串S1中的位置是9。 5. 一个非空广义表的表头（ ）。A不可能是子表 B只能是子表C只能是原子 D可以是子表或原子6.完全二叉树()满二叉树A 不一定是 B一定不是 C一定是 D不能确定关系7. 用链表表示线性表的优点是（ ）A. 便于随机存取B. 便于插入和删除操作C. 花费的存储空间较顺序存储少D. 元素的物理顺序与逻辑顺序相同8.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边()。An(n-1)/2 Bn-1 Cn Dn+19.下列查找方法中哪一种不适合元素的链式存储结构()A顺序查找 B分块查找 C二分查找 D散列查找10.下面哪种排序方法稳定性最好()。 A希尔排序 B冒泡排序 C快速排序 D堆排序二、填空题（本题共 20分）1. 数据的逻辑结构可以分为两大类：_和_。2. 在二叉树的第i层上最多有_个结点。3. 无向图中恰好有_条边，才称为无向完全图。4. 用单链表方式存储的线性表，存储每个结点需要有两个域，一个是_，另一个是_。5. 设二维数组A56的每个元素占4个字节，已知LOC（a00）=1000，则A一共占用_字节。如果按行优先存储时，a25的起始地址是_。6. 3个结点的树有_种形态，3个结点的二叉树有_种形态。7. 一个广义表为（a，（a，b），d，e，（i，j），k），则该广义表的深度为_。8. 栈的插入操作在_进行，删除操作在_进行。9. 在二叉树中，结点的最大度数是_。10. 判定一个有向图中是否存在回路，即是否含有环，可以使用_方法。11. 二分查找的效率较高，但是要求查找表中的关键字_，并且要求表的存储为_。12. 在构造散列表的过程中，不可避免会出现冲突，通常解决它的方法有_和_。13从任何一个结点开始都能成功查找其他结点的单链表是 表。三、应用题（本题共 50分，每题10分）1. 一棵二叉树如右面的图所示，要求： （1）写出对此二叉树进行中序遍历时得到的结点序列。 （2）画出由此二叉树转换得到的森林。2. 已知图G的邻接表如下，写出从顶点O出发的深度优先和广度优先遍历的顶点序列。 0 0 2 1 3 1 0 0 2 2 0 3 0 1 3 0 2 03. 对于下面所示的连通图，写出由Prim算法生成的最小生成树。 4.下图所示为AOE网，求其关键路径和关键活动。 四、算法填空题（本题共10 分）下列两个算法分别为二分查找算法和冒泡排序算法，阅读下面程序代码，填充空白位置，使算法完整。#Define n 10typedef int KeyType;typedef struct KeyType key; NodeType;typedef NodeType SeqListn+1;1. int BinSearch (SeqList R,KeyType k)int low=1,high=n,mid;while(lowk) _1_; else _2_;return 0; 2. void BubbleSort (SeqList R) int i,j Boolean exchange; For( i=1;in;i+) exchange=false;for(j=1;j=n-I;j+) if(Rj+1.keyright=s; s-left=q; q-right-left=s; s-right=q-right;B.s-left=q; q-right=s; q-right-left=s; s-right=q-right;C.s-left=q; s-right=q-right; q-right-left=s; q-right=s;D.以上都不对9.由下列三棵树组成转的森林换成一棵二叉树为( )10. for（i=0；im；i+）for（j=0；jt；j+）cij=0；for（i=0；im；i+）for（j=0；jt；j+）for（k=0；knext-next!=h) p=p-next; p-next=h; 后（其中，p-next为p指向结点的指针域），则( )A. p-next指针指向链尾结点 B. h指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点 15.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )A.高度等于其结点数B.任一结点无左孩子 C.任一结点无右孩子D.空或只有一个结点二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的逻辑结构通常包括集合、线性结构、_和图状结构。17给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过 次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。18树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的 关系。19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为_。20.数据表示和_是程序设计者所要考虑的两项基本任务。21.在循环队列中，存储空间为0n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 _。22.深度为k的二叉树至多有 _个结点，最少有 _个结点。23在堆排序和快速排序中，若原始记录已基本有序，则较适合选用 。24.在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_的。26.三个结点可构成_种不同形态的二叉树。27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值，若ai的值大于ai+1的值，则交换ai和ai+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_。28.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中_个用于链接孩子结点。三、应用题（本大题共5小题，每小题6分，共30分）29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。30有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。31.已知某二叉树的顺序存储结构如图所示，试画出该二叉树，并画出其二叉链表表示。ABCDEFG32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。33.请按照数列28，45，33，12，37，20，18，55的先后插入次序，生成一棵二叉排序树。四、算法设计题(本大题共3小题，共14分)34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。（4分）35.某带头结点的单链表的结点结构说明如下： （6分）typedef struct node1 int data; struct node1 *next node；试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。36.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。（4分）参考答案一、选择题（本题共30分,每题2分）1、 C 2、B 3、C 4、B 5、B 6、C 7、B 8、C 9、A 10、C 11、B 12、D 13、C 14、D 15、A二、填空题（本题共26分,每小题2分）16、树状结构 17、 n-118、逻辑 19、 n/220、数据处理 21、 front=(rear+1)%n22、2k-1，k 23、堆排序24、中序 25、有序26、5 27、冒泡排序28、n-1三、应用题（本题共30分，每小题6分）29、ABCDG后序序列：CDBGFEA (3分)FE(3分)30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);ACDEFG32、第1趟： 37 38 73 52 40 64 56 43第2趟： 37 38 43 52 40 64 56 73第3趟： 37 38 40 43 52 64 56 73第4趟： 37 38 40 43 52 64 56 73第5趟： 37 38 40 43 52 56 64 73第6趟： 37 38 40 43 52 56 64 7331、BACDEFG A B NULL C ROOT D E F G 33、2812452018335537四、算法设计题（本题共14分）34、(4分)typedef struct node *pointer;struct node datatype data; pointer next;typedef pointer lklist;void insert_lklist(lklist head,datatype x,int i) pointer *p,*s;p=head; j=0; while(p-next!=NULL)&(jnext;j+; if(j!=i-1) printf(不存在第i个位置); break();else s=malloc(size);s-data=x; s-next=p-next; p-next=s;35、(6分)int copy(node *head1,node *head2) Node *p,*s; P=head1-next; If(p!=NULL) *r=malloc(size); r-data=p-data; head2=r; p=p-next; else head2=NULL; Return(0); While(p!=NULL) *s=malloc(size); s-data=p-data; r-next=s; r=s;p=p-next; r-next=NULL; return(1);36、（4分）typedef char DataType;typedef struct nodeDataType data;struct node *lchild, *rchild; BinTNode;typedef BinTNode *BinTree;int nodes(BinTree T)int num1,nu