数据结构期末试卷A-下hqu

《数据结》试卷（数学科学院11-12学年下期学

号：

姓

名：

日期：题

号

一

二

三

四

五

总

分得

分一选题每题2分共30分，写答纸）1.下程段时复度（），；(s<n){s=s+i；i++}O(n)B.O(n)C.D.2.每结有仅一直前和个(无直后(一个点外的据构为）。A.树结B.网状构C.线性构层结3.在有结的链head中要表插一由针p指的点则行()p->next=head;p->next=head->next;head->next=p;p->next=head;head=p;p->next=head;4.一栈输序为ac则列列不能栈输出列是。bcB.baC.cbD.abc5.无完图G有n个点则的的数（）2B.n(n-1)C.n(n-1)/26.若棵叉有10个度为2的点5个为1的结，度0的结数（）B.11D.不确7.设通G中边，则下的4个列，符深优遍的列（）8.队是种）的性。A.先先先进出C.只能入D.能除9.已二排树G要出结的序列则采的历法（）A.按遍B.先序历中遍D.后遍设按从到、左右顺从1开对全叉进顺编，编为i结的孩结的号（）2i+1B.2iC.i/22i-1对列159，7820，，4)行序，一排后序变(，，-1，，20，，15)则用排方是）。A.选B.快速C.希尔D.冒泡若18个元素有表放一数A[19]，一元素A[1]中，进二查，查A3的较序的标次()1239，，，3C.，，9423

设序环列Q[M-1]头针尾针别F和R头针F总指队元的当位，指R总是向尾素后位，该环列的素个为）。B.F-RC.(R-F+M)MD.(F-R+M)％M设一10阶的三矩阵A包对线，照上到、左右顺存到连的55个储元每数元占1个字节存空则地与A[0][0]的址差（）B.19C.28在个head头结点针非单环表指p指向尾点条（->data-1B.p->=NULL->next->next=head->nexthead二填（题2，，写答纸）1.数元之的系计机有种同的示法【】和】。2.线表L=(a1,a2,„an)数组示假删表任元的率同则除个元平需移元的数【】3.一中算表式（A+B），对的缀表式【】4.设棵全叉中个点则二树深为】若二链作该全叉的储构则有个指域5.假一树广表示（，DEFG，HIJ），树所的点为【】，的度【】树度【】。6.若(，，6，78)作叶结的权构哈曼，其权径度【】。7.设向G中向的合E={<v1,v2>,<v1,v3>,<v2,v5>,<v2,v6>,<v3,v5>,<v3,v6>,，则图个扑序列别【】和】。一组录关字(46，7956，38，40，84)，则用速序方，第一记录基得的次分果【】9.已广表A=(x数GetHead(GetHead(GetTail(A)))的运结是】。.一队的队列234，则队列【】。设无图（如图示）则最生树所边权之为4。三判题每题1，分请在卷上．不是队操还入操，顺存结上需要虑溢”况（）．当二排树插一结，该点定为子结。）．分查的本想首在引中行找以确定定关字能在块号然再相的内行序找（）．带无图最生树唯的（）．哈曼中有数1的点（）．对通进深优遍可访到图的有点。）．稀矩的缩储以一三组来示疏阵中非0元。）．由转成叉，二树右树一为。．线表的有素有个驱素后元。完全叉中叶结只能最两中出。）

四应题每分共30分1.下程段功是现泡序法请在划处上确语。voidr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}ifreturn；}}2.对键序(26，60，14，，45，进行序堆序写构的始小根)前趟建之序状。初堆第趟第趟3.设列数(key)=key％11散地空为，对关字列27，13，55，3218，49，3843)线探法决突构建列。已前4个键构的列如所，将余5个键填表相的置4.已一二树前遍和序历列分为ABCDEFG和CBDAEGF，要求:画此叉;给后遍序;画中前线二树。5.下所的林求树a的根列后序；求森先序和序列将森转为应二叉。A

GB

C

HD

I

J(b)

K五算设（）1.假以链表线表单表类定义下structdatanode；LinkNode，*LinkList；设判单表元是是增算。

参答一、选题（每小题分，共）题答

A

A

B

C

C

B

A

A

C

B

1415CDCD二、填题（每小题分，共22）

顺映(n-1)/2AB+C/DEF-*-V1,V2,V3,V6,V5,V4或V1,V2,V3,V5,V6,V440,38,46,56,79,84(a,b)

非序像V1,V3,V2,V6,V5,V4或V1,V3,V2,V5,V6,V4三、判题（每小题分，共10）题答

1Y

2Y

3Y

4N

5Y

6Y

7Y

8N

9N

10Y

四应用题1.答r[j+1]=r[j]解:初始堆:13,18,60,第趟32,26,45,7第趟14,26,45,解:247891043132449324.解:(1)叉如EDF后遍历列中前驱索叉如D

5.解: