《数据结构05有答案》由会员分享，可在线阅读，更多相关《数据结构05有答案（6页珍藏版）》请在金锄头文库上搜索。
1、山东06年专升本数据结构试卷一、填空题：(每空1分，共22分)1. 数据结构按结点间的关系被分为四种逻辑结构，分别是集合、线性结构、图 和树结构四种。2. 若经常需要对线性表进行插入和删除操作，则最好采用链式存储结构，若经常需要对线性表进行查找操作，则最好采用顺序存储结构。3. 在一个单链表中删除指针p所指向结点的后继结点时，需要把 p-next-next的值赋给p-next指针域。4. 在一个长度为n的顺序存储的线性表中，向第i个元素(lWiWn+1)位置插入一个新元素时，需要从后向前依次后移_n-i-1个元素。5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为0(n)表
2、尾插入元素的时间复杂度为0(1)。6. 设元素1，2,3,4,5依次进入栈S,若要在输出端得到序列34251，则应进行的操作序列为 push ( S,1 ),push(S,2),push(s,3),pop(S),push(S,4),pop(S),pop(s),push(s,5),pop(S),pop(S)。7. 已知广义表 A= (a,b,c), (d,e,f )，则广义表运算 head (tail (tail (A) =e8. 一个NXN的对称矩阵，如果以行为主序或以列为主序存入内存，则其存储容量为n(n+1)/2。9. 在一棵树中,_I根_结点没有前驱结点，其余每个结点有并且只有一个前驱，
3、可以有任意多个后继结点。10在分块查找方法中，首先查找索引，然后再查找相应的块。11. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要nn条边。12. 在对n个元素进行直接插入排序的过程中，共需要进行。13. 顺序查找法的平均查找长度为(n+1)/2；分块查找法(以顺序查找确定块)的平均查找长度是(s2+2s+n)/2S 。二、选择题(每题2分，共30分)1. 在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新的结点，则 需要相继修改()个指针域的值。A. 2 B. 3 C. 4 D.62. 不带头结点的单链表L为空的判定条件是()A. L= =NULL B. L-ne
4、xt= =NULL C. L-next= =L D. L!=NULL3. 循环队列用数组Am(下标从0到m1)存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是()B. rear front+ 1C. rear front 1 D. rear front4. 深度为K的二叉树所含叶子的个数最多为()A. 2K B. KC. 2k-1 D. 2k-i5一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()A. e,d,c,b,a B. d,e,c,b,aC. d,c,e,a,b D. a,b,c,d,e6. 如图所示的4棵二叉树中，不是完全二叉树的是()
5、A)B)D)7. 利用n个值生成的哈夫曼树中共有（）个结点A n B n+1 C2n D 2n 18有一个有序表为1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，当二分法查 找值为82的结点时，（）次比较后查找成功。A. 1B. 2C. 4D. 89. 若对n个元素进行归并排序，则进行每一趟归并的时间复杂度为（）A. 0（1）|b. 0（n）C. O （logn） D. 0（m）10. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的 一端的方法，称为（）A.希尔排序 B.归并排序C.插入排序起泡排序11. 如果要求
6、一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（）查 找方法。A.分块B.顺序C.折半D.散列12. 如图所示的带权无向图，在该图的最小生成树中各条边上权值之和为（）A. 31 B. 38 C. 36 D. 4313. 有一个MXN的矩阵A,若采用行序为主序进行顺序存储，每个元素占用8个字节，则 A （lWiWM,lWjWN）元素的相对字节地址（相对首元素地址而言）为（）i,jA. （i 1）X N+j）X8 B. （i 1）XN+j 1）X8C. （iXN+j 1）X8D. （i 1）XN+j + 1）X814. 某二叉树的先序遍历结点访问顺序是abdgcefh,中序遍历的结点访
7、问顺序是dgbaechf, 则其后序遍历的结点访问顺序是（）A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca15如图所示，一个图若从顶点a出发按广度优先搜索法进行遍历，则可能得到的一种顶点 序列为（ ）A . abecdefB. abcefd C. aebcfd D. aedfeb三、算法设计题（第一题8分，第二题7分，第三题8分，共23分）1. 已知单链表A,B和C为三个元素值递增有序的线性表，现要求对表A作如下运算：删去 那些既在表B中出现又在表C中出现的元素。2.设树b是一棵采用链式结构存储的二叉树，写出b的交换左右子树的递归算法。Bitre
8、e swap(Bitree &b) Bitree t, t1, t2;if (b= =NULL) t=NULLt=(Bitree)malloc(sizeof(Bitnode); 若 b 不为空，则复制一个根结点t-data=b-data; t1=swap(b-lchild);t2=swap(b-rchild);-lchild=t2;-rchild=tl;return(t);datanext其中 data3.已知带头结点的线性链表list,链表中结点类型Node为: 为数据域， next 为指针域。请写一算法，将该链表按结点数据于的值从小到大重新链接。 要求链接过程中不得使用除该链表以外的任何结
9、点空间。Typedef Node *LNode;void sort (LNode &list) /采用直接插入排序的方法 LNode head,p,s,q,rJhead=list;p=head-nextnext;headnextnext=NULL;wyhile（p!二N q=head;ULL）while（qnext!二NULL&qnextdatapdata）q=qnext;r二pnextpnext=qnext; qnext=p;试卷答案一、填空题1. 集合结构 图结构 （次序无先后）2. 链式 顺序3. pnextnext4. ni15. O（n）O（1）6. push（S,3）pop（S）
10、push（S，5）7. e8n（n1）/29根前驱（或双亲）后继（或孩子）10索引 块11n112n113（n+1）/2（s2+2s+n）/2S二、选择题（每题2 分，共 30分）1C 2.A 3.A 4.D 5. C 6.C 7.d 8.C 9.B10. D 11. A 12 C 13 B 14.D 15.B三、算法设计题（第一题8分，第二题7分，第三题8 分，共23分） 1.void deleteA（Linklist &A,Linklist B, Linklist C） Linklist p,q,r,t,s=Ap=Anext;q=Bnext; r=Cnext; while（p!=NULL）
11、&（q!=NULL）&（r!=NULL） if（pdata= =qdata）&（pdata = =rdata） snext=pnext;t=p;p=s-next;free(t);q=q-next;r=r-next;else if(p-dataq-data)q=q-next; if(p-datar-data)r=r-next;else if(p-datadata)|(p-datar-data) s=p;p=p-next;2.Bitree swap(Bitree &b) Bitree t, t1, t2;if (b= =NULL) t=NULLelset=(Bitree)malloc(sizeof
12、(Bitnode); /若 b 不为空，则复制一个根结点 t-data=b-data;t1=swap(b-lchild);t2=swap(b-rchild);t-lchild=t2;t-rchild=t1;return(t);3Typedef Node *LNode;void sort (LNode &list) /采用直接插入排序的方法 LNode head,p,s,q,r;head=list;p=head-next-next;head-next-next=NULL;while(p!=NULL) q=head; while(q-next!=NULL&q-next-datadata) q=q-next;r=p-nextp-next=q-next; q-next=p; p=r;
