XX理工大学数据结构期末试卷.doc

一、选择题每题2分共20分1假设长度为n的线性表(a1, a2, an)采用顺序存储，删除它的第i个数据元素，需要依次向前移动 个数据元素。 A. n-ii-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算术表达式ab+c/d的逆波兰式是_。 A. abcd+/ B. abc/d+ C. abcd/+ D. ab+cd/5循环队列用数组A0，m-1存放其元素值，其头尾指针分别是front和rear，那么当前队列中的元素个数是。A(rear-front+m)%mBread-front+1Cread-front-1 Dread-front6设二维数组a0m-10n-1按行优先顺序存储在首地址为loc(a00)的存储区域中，每个元素占d个单元，那么aij的地址为_。A. loc(a00) +( in+ j) d B. loc(a00) +(jm+i) d C. loc(a00) +(j-1)n+i-1) d D. loc(a00) +(j-1)m+i-1) d7对于二叉树来说,第i层上至多有_个结点。 A2i B 2i-1 C2i-1 D2i-1-18有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100，当二分查找值为82的结点时， 次比拟后查找成功。A1 B2 C4 D89设哈希表长m=11，哈希函数Hkey=key%11。表中已有4个结点：addr15=4， addr38=5，addr61=6，addr84=7，其余地址为空，如果线性探测再散列处理冲突，关键字为49的结点地址是 。 A3 B5 C8 D910用某种排序方法对线性表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二叉树的扩展前序序列：FKHBEGADC.请画出该二叉树并写出该树的中序和后序序列。12分2画出以下树对应的二叉树。10分G=,其中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(“%dn,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(%cn,x);运行结果是 。 3int 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 (krmid) low=mid+1;else imid;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;i0;i-)p =(linklist)malloc(sizeof(lnode); scanf(“%d,&p-data); B ; C ; 2完成以下插入排序算法。typedef struct nodeint key; int data;NODE;void insert(NODE r ,int n) / r0为哨兵int i,j; for(i=2;inext=NULL B:p-next=head-next C: head-next=p 2. A: ri.keyri-1.key B:r0.keyrj.key C:rj+1=r0 【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】页脚下载后可删除，如有侵权请告知删除！