全真试题(四) 本试卷分两部分,第一部分为选择题,1页至2页,第二部分为非选择题,3页至12页,共12页;选择 题30分,非选择题70分,满分100分。考试时间150分钟。 第一部分选择题(共30分) 单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个是符合 题目要求的,请将其代码填在题后的括号内。错选或未选均无分。 1.下列各式中,按增长率由小至大的顺序正确排列的是() A. n, n!, 2, n3/ B n3/2, 2, nlogn, 2100 C: 2, logn, nlogn, n/2 D2100, logn, 2n,n" 2若要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是() p->next=s; B. p->next=s; S->next=p->next C. p->next=s->next; s->next=p; D S->next=p p->next=s->next; 3.若要在O(1)的时间复杂度上实现两个循环链表头尾相接,则应对两个循环链表各设置一个指针,分别 指向() A.各自的头结点 B各自的尾结点 C.各自的第一个元素结点D.一个表的头结点,另一个表的尾结点 4栈的两种常用存储结构分别为() A顺序存储结构和链式存储结构B顺序存储结构和散列存储结构 C.链式存储结构和索引存储结构D链式存储结构和散列存储结构 5已知循环队列的存储空间为数组data[21,且当前队列的头指针和尾指针的值分别为8和3,则该队的当 前长度为() C.16 D.17 6已知在如下定义的链串结点中,每个字符占1个字节,指针占4个字节,则该链串的存储密度为() typedef struct node char date[ 8] struct node next 9 Link Str Node 7应用简单的匹配算法对主串s=“ BDBABDABDAB”与子串t=“BDA”进行模式匹配,在匹配成功时 进行的字符比较总次数为() B.9 C.10 8.二维数组A[2010].用列优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200 则元素A[8]9]的存储地址为() A.574 B.576 C.578 9.对广义表L=(a.b),c,d)进行操作tail(head(L)的结果是() B (d) D.(b) 10已知一棵树的前序序列为 ABCDEF,后序序列为 CEDFBA,则对该树进行层次遍历得到的序列为() AABCDEF B.ABCEFD C. ABFCDE D.ABCDFE 11.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构,则计算该有向图中某个顶点出度的时 间复杂度为() O(n) B O(e) O(n2) 12.在关键字序列(12,23,34,45,56,67,78,89,91)中二分查找关键字为45,89和12的结点时, 所需进行的比较次数分别为() B.4,3,3 C.3,4,4 D.3,3,4
全真试题（四） 本试卷分两部分，第一部分为选择题，1 页至 2 页，第二部分为非选择题，3 页至 12 页，共 12 页；选择 题 30 分，非选择题 70 分，满分 100 分。考试时间 150 分钟。 第一部分 选择题（共 30 分） 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个选项中只有一个是符合 题目要求的，请将其代码填在题后的括号内。错选或未选均无分。 1.下列各式中，按增长率由小至大的顺序正确排列的是（ ） A. n ,n!,2n ,n3/2 B.n 3/2 ,2 n ,nlogn,2100 C.2 n , logn, nlogn, n3/2 D.2 100, logn, 2n , nn 2.若要在单链表中的结点*p 之后插入一个结点*s，则应执行的语句是（ ） A.s-＞next=p-＞next; p-＞next=s; B.p-＞next=s; s-＞next=p-＞next C.p-＞next=s-＞next; s-＞next=p; D.s-＞next=p;p-＞next=s-＞next; 3.若要在 O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别 指向（ ） A.各自的头结点 B.各自的尾结点 C.各自的第一个元素结点 D.一个表的头结点，另一个表的尾结点 4.栈的两种常用存储结构分别为（ ） A.顺序存储结构和链式存储结构 B.顺序存储结构和散列存储结构 C.链式存储结构和索引存储结构 D.链式存储结构和散列存储结构 5.已知循环队列的存储空间为数组 data[21]，且当前队列的头指针和尾指针的值分别为 8 和 3，则该队的当 前长度为（ ） A.5 B.6 C.16 D.17 6.已知在如下定义的链串结点中，每个字符占 1 个字节，指针占 4 个字节，则该链串的存储密度为（ ） typedef struct node{ char date[8]; struct node * next; } LinkStrNode; A.1/4 B.1/2 C.2/3 D.3/4 7.应用简单的匹配算法对主串 s=“BDBABDABDAB”与子串 t=“BDA”进行模式匹配，在匹配成功时， 进行的字符比较总次数为（ ） A.7 B.9 C.10 D.12 8.二维数组 A[20][10]采用列优先的存储方法，若每个元素占 2 个存储单元，且第 1 个元素的首地址为 200， 则元素 A[8][9]的存储地址为（ ） A.574 B.576 C.578 D.580 9.对广义表 L=((a,b),c,d)进行操作 tail (head (L))的结果是（ ） A.(c,d ) B.(d ) C.b D.(b) 10.已知一棵树的前序序列为 ABCDEF，后序序列为 CEDFBA，则对该树进行层次遍历得到的序列为（ ） A.ABCDEF B.ABCEFD C.ABFCDE D.ABCDFE 11.一个含 n 个顶点和 e 条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时 间复杂度为（ ） A.O(n) B.O(e) C.O(n+e) D.O(n2 ) 12.在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为 45，89 和 12 的结点时， 所需进行的比较次数分别为（ ） A.4，4，3 B.4， 3， 3 C.3，4，4 D.3，3，4
13.下列排序方法中,最好与最坏时间复杂度不相同的排序方法是 A.冒泡排序 B.直接选择排序 C.堆排序 D归并排序 14.已知含10个结点的二叉排序树是一棵完全二叉树,则该二叉排序树在等概率情况下查找成功的平均查 找长度等于() A.1.0 B.2.9 C.3.4 15在下列各种文件中,不能进行顺序查找的文件是() A.顺序文件 B索引文件 C散列文件 D多重表文件 第二部分非选择题(共70分) 填空题(本大题共10小题,每小题2分,共加0分)请在每小题的空格中填上正确答案。错填、不填 均无分 6抽象数据类型是指数据逻辑结构及与之相关的 17.已己知在结点个数大于1的单循环链表中,指针p指向表中某个结点,则下列程序段执行结束时,指针q 指向结点*p的 结点 qp while(q->nextI=p)q=p->next 18假设S和Ⅹ分别表示进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA”的操作序列为 SSXSXX, 则由“a*b+cd得到“ab*cd/+”的操作序列为」 19在文本编辑程序中查找某一特定单词在文本中出现的位置,可以利用串的 运算 20.假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中,则数组Q的大小至少 为 21在含100个结点的完全二叉树中,叶子结点的个数为 2在无向图中,若从顶点a到顶点b存在 则称a与b之间是连通的 23如果排序过程不改变 之间的相对次序,则称该排序方法是稳定的 24索引顺序查找适宜对 的顺序表进行查找 25文件的检索操作可按检索条件不同分为下列四种询问,它们是简单询问、范围询问、函数询问 及 三、解答题(本大题共4小题,每小题5分,共20分) 26画出下图所示二叉树的中序线索链表的存储表示 27已知图G=(V,E),其中 V=fa, b, c, d, el E={(a,b),b,d),cb),c,d),(de),(e,a)e,c)}。 (1)画出图G (2)画出图G的邻接表 28已知自顶向下的二路归并排序的算法如下所示,按此算法对关键字序列(55,28,73,91,37,64,19 82,46)进行排序,列出算法执行过程中前5次调用 Merge函数进行归并之后的关键字序列 void Merge SortDC(SeqListR, int low, int high) {用分治法对R[ow.high进行二路归并排序 int mid- if (low<high ∥区间长度大于1 mid=(low+high)/2 ∥分解 MergeSortDO(Rlow,mid);∥递归地对Rlow.mid]排序 MergeSort(Rmid+l,high),∥递归地对R[mid+1.high排序 Merge(r, low, mid, high); ∥组合,将两个有序区归并为一个有序区
13.下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（ ） A.冒泡排序 B.直接选择排序 C.堆排序 D.归并排序 14.已知含 10 个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查 找长度等于（ ） A.1.0 B.2.9 C.3.4 D.5.5 15.在下列各种文件中，不能进行顺序查找的文件是（ ） A.顺序文件 B.索引文件 C.散列文件 D.多重表文件 第二部分 非选择题（共 70 分） 二、填空题（本大题共 10 小题，每小题 2 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填 均无分。 16.抽象数据类型是指数据逻辑结构及与之相关的 。 17.已知在结点个数大于 1 的单循环链表中，指针 p 指向表中某个结点，则下列程序段执行结束时，指针 q 指向结点*p 的 结点。 q=p; while (q-＞next!=p)q=p-＞next; 18.假设 S 和 X 分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为 SSXSXX， 则由“a*b+c/d”得到“ab*cd/+”的操作序列为 。 19.在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的 运算。 20.假设以行优先顺序将一个 n 阶的 5 对角矩阵压缩存储到一维数组 Q 中，则数组 Q 的大小至少 为 。 21.在含 100 个结点的完全二叉树中，叶子结点的个数为 。 22.在无向图中，若从顶点 a 到顶点 b 存在 ，则称 a 与 b 之间是连通的。 23.如果排序过程不改变 之间的相对次序，则称该排序方法是稳定的。 24.索引顺序查找适宜对 的顺序表进行查找。 25.文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问 及 。 三、解答题（本大题共 4 小题，每小题 5 分，共 20 分） 26.画出下图所示二叉树的中序线索链表的存储表示。 27.已知图 G=（V，E），其中： V={a,b,c,d,e}, E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。 （1）画出图 G； （2）画出图 G 的邻接表。 28.已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19， 82，46）进行排序，列出算法执行过程中前 5 次调用 Merge 函数进行归并之后的关键字序列。 void MergeSortDC(SeqList R, int low, int high) {//用分治法对 R[low.. high]进行二路归并排序 int mid; if (low＜high＝{ //区间长度大于 1 mid=(low+high)/2 //分解 MergeSortDC(R,low,mid); //递归地对 R[low..mid]排序 MergeSortDC(R,mid+1,high); //递归地对 R[mid+1..high]排序 Merge(R,low,mid,high); //组合，将两个有序区归并为一个有序区 F A B C D E K
i //Merge SortDC 29由于元素的插入先后次序不同,所构成的二叉排序树可能有多种形态。请画出4棵含1,2,3,4,5, 6六个元素且以1为根、深度为4的二叉排序树 四、算法阅读题(本大题共4小题,每小题5分,共20分) 30L为一个带头结点的循环链表。函数f30的功能是删除L中数据域daa的值大于c的所有结点,并由这 些结点组建成一个新的带头结点的循环链表,其头指针作为函数的返回值。请在空缺处填入合适的内容, 使其成为一个完整的算法。 Link List f30(LinkList L, intc) LinkList Lc, p, pre pre=L, Lc=(LinList )malloc(sizeof(ListNode)) Lc->next=Lc. while(pl=L) if (p->data pre->next=p->next; Lc->next= pre-p eturn l 31设栈S=(1,2,3,4,5,6,7)其中7为栈顶元素。 (1)写出调用f31(&S)后的S (2)简述函数f31中第1个循环语句的功能。 void f31(Stack*S) Queue Q Stack T InitQueue(&Q) InitStack(&T) while(STack Empty(S)) if((i=li)!=0) Push(&T, Pop(S)); else EnQueue(&Q, Pop(S) while(STack Empty(&D) Push(S, Pop(&D)); while(! Queueempty(&Q))
} }// MergeSortDC 29.由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出 4 棵含 1，2，3，4，5， 6 六个元素且以 1 为根、深度为 4 的二叉排序树。 四、算法阅读题（本大题共 4 小题，每小题 5 分，共 20 分） 30.L 为一个带头结点的循环链表。函数 f30 的功能是删除 L 中数据域 data 的值大于 c 的所有结点，并由这 些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容， 使其成为一个完整的算法。 LinkList f30(LinkList L, intc) { LinkList Lc,p,pre; pre=L; p= (1) ; Lc=(LinList)malloc(sizeof(ListNode)); Lc-＞next=Lc; while (p!=L) if (p-＞data＞c) { pre-＞next=p-＞next; (2) ; Lc-＞next=p; p=pre-＞next; } else { pre=p; (3) ; } return Lc; } 31.设栈 S=（1，2，3，4，5，6，7）其中 7 为栈顶元素。 （1）写出调用 f31(&S)后的 S； （2）简述函数 f31 中第 1 个循环语句的功能。 void f31 (Stack * S) { Queue Q; Stack T; int i=0; InitQueue(&Q); InitStack(&T); while (!StackEmpty(S)) if ((i=!i)!=0) Push(&T,Pop(S)); else EnQueue(&Q,Pop(S)); while (!StackEmpty(&T)) Push(S,Pop(&T)); while(!QueueEmpty(&Q))
Push(s, DeQueue(&Q)) 32图的邻接矩阵表示描述如下: #define maxNum 20 ∥图的最大顶点数 typedef struct( char vexs MaxNum] ∥}符类型的顶点表 nt edges[ Max Num [ MaxNum];∥邻接矩阵 /图的顶点数和边数 i MGraph; ∥图的邻接矩阵结构描述 阅读下列算法,并回答问题: (1)对于下列图G的邻接矩阵,写出函数调用F32(&G,3)的返回值: 01111 00100 00010 11000 100110 (2)简述函数f32的功能 (3)写出函数f32的时间复杂度 int f32(MGraph *G, int 1) int d=0, 5; for(=0,jn,j++) if(G->edges[il[)d++ if( G->edges[l[i)d++ return d 33阅读下列算法并回答问题: (1)设数组L[18]的初值为(4,-3,7,-1,-2,2,5,-8),写出执行函数调用f33(L,8)之后的L[.8] 中的元素值 (2)简述函数f33的功能。 void f33(intR[L, int n) int low =1. high=n while(low 0) high--. f (low <high= R[low++]=R[high whilelow<high & r[low <o) low++
Push(S,DeQueue(&Q)); } 32.图的邻接矩阵表示描述如下： #define MaxNum 20 //图的最大顶点数 typedef struct{ char vexs[MaxNum]; //字符类型的顶点表 int edges[MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数 }MGraph; //图的邻接矩阵结构描述 阅读下列算法，并回答问题： （1）对于下列图 G 的邻接矩阵，写出函数调用 F32（&G,3）的返回值； 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 （2）简述函数 f32 的功能； （3）写出函数 f32 的时间复杂度。 int f32(MGraph *G, int i) { int d=0, j; for (j=0; j＜G-＞n; j++) { if (G-＞edges[i][j])d++; if( G-＞edges[j][i])d++; } return d; } 33.阅读下列算法并回答问题： （1）设数组 L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用 f33（L，8）之后的 L[1..8] 中的元素值； （2）简述函数 f33 的功能。 void f33(intR[ ],int n) { int x =R [1]; int low =1, high=n; while (low＜high) { while (low＜high && R[high]＞0) high--; if (low＜high＝ { R[low++]=R[high]; while (low＜high && R[low] ＜0) low++;
RIhigh--=R[low Rlow]=x 五、算法设计题(本题共10分) 34假设二叉链表作为二叉树的存储结构,其特点结构为: Child Rchild 依照如下给定的函数34的原型,编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中, 参数leve为函数执行过程中T当前所指结点的层次,其初值为1:lmin与+max分别为叶子结点的最小 层次与最大层次,它们的初值均为0。 void f34(BinTree T, int level, int *Imin, int*Imax)
R[high--]=R[low]; } } R[low]=x; } 五、算法设计题（本题共 10 分） 34.假设二叉链表作为二叉树的存储结构，其特点结构为： lchild data Rchild 依照如下给定的函数 f34 的原型，编写求二叉树 T 中叶子结点所在的最小层次与最大层次的函数。其中， 参数 level 为函数执行过程中 T 当前所指结点的层次，其初值为 1；*lmin 与*lmax 分别为叶子结点的最小 层次与最大层次，它们的初值均为 0。 void f34(BinTree T, int level, int *lmin, int *lmax);