一、选择题（每题2分共20分）1．若长度为n的线性表(a1, a2,…, a n)采用顺序存储，删除它的第i个数据元素，需要依次向前移动个数据元素。

A. n-iB. n+iC.n-i+1D.n-i-12．在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行_____。

A. p->next=q->next; q->next=p;B. q->next=p->next; p=q;C. p->next=q->next; p->next=q;D. q->next=p->next; p->next=q;3．栈是一种的线性表。

A. 只允许在一端进行插入和在另一端进行删除B. 只允许在一端进行插入和删除C. 只允许在两端进行插入和删除D. 允许在中间部位进行插入和删除4．算术表达式a×b+c/d的逆波兰式是______。

A. ab×cd+/B. ab×c/d+C. ab×cd/+D. ab+×cd/5．循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。

A．(rear-front+m)%m B．read-front+1C．read-front-1 D．read-front6．设二维数组a[0…m-1][0…n-1]按行优先顺序存储在首地址为loc(a00)的存储区域中，每个元素占d个单元，则a ij的地址为________。

A.loc(a00) +( i×n+ j) ×dB. loc(a00) +(j×m+i) ×dC. loc(a00) +((j-1)×n+i-1) ×dD. loc(a00) +((j-1)×m+i-1) ×d7．对于二叉树来说,第i层上至多有____个结点。

A．2i B． 2i-1 C．2i-1 D．2i-1-18．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当二分查找值为82的结点时，（）次比较后查找成功。

A．1 B．2 C．4 D．89．设哈希表长m=11，哈希函数H（key）=key%11。

表中已有4个结点：addr（15）=4， addr （38）=5，addr（61）=6，addr（84）=7，其余地址为空，如果线性探测再散列处理冲突，关键字为49的结点地址是。

A．3 B．5 C．8 D．910．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：25,84,21,47,15,27,68,35,2015,84,21,47,25,27,68,35,2015,20,21,47,25,27,68,35,8415,20,21,25,47,27,68,35,84．．15,20,21,25,27,35,47,68,84则采用的排序方法是（）。

A．冒泡排序 B．快速排序 C．归并排序 D．选择排序二、求解题1．已知二叉树的扩展前序序列：FKHφφBEφφφGAφφDφCφφ.请画出该二叉树并写出该树的中序和后序序列。

（12分）2．画出下列树对应的二叉树。

（10分）3.给定无向图G=<V,E>,其中V={a,b,c,d,e},E={(a,b),(a,e),(b,e),(b,c),(c,e),(e,d)}.请画出图G的邻接矩阵,邻接表。

从结点a出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。

(12分)4．从空的二叉排序树开始依次插入30，18,11,17,7,5,13,41,29,37,23,19。

画出该二叉排序树。

（9分）5．分别写出对序列 10,18,11,17,7,5,13,41,29,37,23,19,25进行快速排序和冒泡排序的过程。

(16分)三、写出下列算法的功能或输出结果1.typedef struct List{ int number;struct List *next;} Node，*Link;void func1(Link p)//p指向单链表{while(p!=NULL){ printf(“%d\n”,p->number);p=p->next;}}功能是。

2.写出下列程序段的运行结果（栈中的元素类型是char）：main( ){ SEQSTACK s,*p;char x, y;p = &s;initstack(p);x = ‘c’; y = ‘k’;push(p,x); push(p,’a′); push(p,y);x = pop(p);push(p,’t′);push(p,’s′);while(!empty(p)){ y = pop(p);printf(″%c″,y);}printf(″%c＼n″,x);}运行结果是。

3．int func3 (int r[ ], int n, int k) { int i,low=0, high=n-1, mid, find=0;while (low<=high &&find==0){ mid=(low+high)/2;if (k<r[mid]) high=mid-1;else if (k>r[mid]) low=mid+1;else ｛i＝mid;find=1;｝}if (!find) return -1;return i;}功能是。

四、读程填空1．下列算法创建n个元素的带头单链表.typedef struct lnode { int data;struct lnode *next;}lnode,*linklist ;void create(linklist &head, int n){linklist p; int i;head=(linklist)malloc(sizeof(lnode));A ;for(i=n;i>0;i--){p =(linklist)malloc(sizeof(lnode));scanf(“%d”,&p->data);B ;C ;}}2．完成下列插入排序算法。

typedef struct node{int key;int data;}NODE;void insert(NODE r[ ],int n) // r[0]为哨兵{int i,j;for(i=2;i<=n;i++)if ( A ){r[0]=r[i];j=i-1;while ( B )r[j+1]=r[j--];C ;}}参考答案一、A D B C A A B C C D二、1. F 1分K G 2分H B A D 2分E C 1分中序序列:HKEBFAGDC 3分后序序列: HEBKACDGF 3分3.邻接矩阵：0100110101010010000111110⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦邻接表：Dfs: a b c e d其他:a e d c bbfs: a b e c d其他:a e b d c , a e b c d5.快速排序：10,18,11,17,7,5,13,41,29,37,23,19,255,7,10,17,11,18,13,41,29,37,23,19,255,7,10,13,11,17,18,41,29,37,23,19,255,7,10, 11, 13,17, 18,41,29,37,23,19,255,7,10, 11, 13,17, 18,25,29,37,23,19,415,7,10, 11, 13,17, 18,19,23,25,37,29,415,7,10, 11, 13,17, 18,19,23,25, 29,37,41冒泡排序：10,18,11,17,7,5,13,41,29,37,23,19,25i=1: 10,11,17,7,5,13,18,29,37,23,19,25,41i=2: 10,11,7,5,13,17,18,29,23,19,25,37i=3: 10,7,5,11,13,17,18,23,19,25,29i=4: 7,5,10,11,13,17,18,19,23,25i=5: 5,7,10,11,13,17,18,19,23三、1.打印p所指的无头单链表2. stack3.用二分查找方法在r数组中查找k四、 1. A: head->next=NULL B:p->next=head->next C: head->next=p2. A: r[i].key<r[i-1].key B:r[0].key<r[j].key C:r[j+1]=r[0]。