1、下列各式中，按增长率由小至大的顺序正确排列的是(       ) 单选题 2分

2、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( ) 单选题 2分

3、若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向( ) 单选题 2分

4、栈的两种常用存储结构分别为( ) 单选题 2分

5、已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( ) 单选题 2分

6、已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为 typedef struct node { char data[8]; struct node *next; } LinkStrNode; 单选题 2分

7、应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为( ) 单选题 2分

8、二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为( ) 单选题 2分

9、对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是( ) 单选题 2分

10、已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为( ) 单选题 2分

11、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为( ) 单选题 2分

12、在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( ) 单选题 2分

13、下列排序方法中，最好与最坏时间复杂度不相同的排序方法是( ) 单选题 2分

14、已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( ) 单选题 2分

15、在下列各种文件中，不能进行顺序查找的文件是( ) 单选题 2分

16、抽象数据类型是指数据逻辑结构及与之相关的（ ）。 填空题 2分

17、已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的（ ）结点。 q=p; while(q->next!=p)q=q->next; 填空题 2分

18、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为（ ）。 填空题 2分

19、在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的（ ）运算。 填空题 2分

20、假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为（ ）。 填空题 2分

21、在含100个结点的完全二叉树中，叶子结点的个数为（ ）。 填空题 2分

22、在无向图中，若从顶点a到顶点b存在（ ），则称a与b之间是连通的。 填空题 2分

23、如果排序过程不改变（ ）之间的相对次序，则称该排序方法是稳定的。 填空题 2分

24、索引顺序查找适宜对（ ）的顺序表进行查找。 填空题 2分

25、文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及（ ）。 填空题 2分

26、画出下图所示二叉树的中序线索链表的存储表示。 简答题 5分

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的邻接表。 简答题 5分

28、已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。 void MergeSorDC(SeqList R, int low, int high) {// 用分治法对R[low..high]进行二路归并排序} int mid; if (low 简答题 5分

29、由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。 简答题 5分

30、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) { LinkList Lc,p,pre; pre=L; p= (1) ; Lc=(LinkList) 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; } (1) (2) (3) 简答题 5分

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=!t)!=0) Push(&T,Pop(S)); else EnQueue(&Q, Pop(S)); while(!StackEmpty(&T)) Push(S,PoP(&T)); while(!QieueEmpty(&Q)) Push(S,DeQueue(&Q)); } 简答题 5分

32、图的邻接矩阵表示描述如下： #define MaxNum 20 //图的最大顶点数 typedef struct { char vexs[MaxNum]; //字符类型的顶点表 int edges[MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数 } MGraph; //图的邻接矩阵结构描述 阅读下列算法，并回答问题： （1）对于下列图G的邻接矩阵，写出函数调用f32(&G,3)的返回值； （2）简述函数f32的功能； （3）写出函数f32的时间复杂度。 int f32(MGraph *G, int i) { int d=0,j; for(j=0;jn;j++) { if (G->edges[i][j]) d++; if (G->edges[j][i]) d++; } return d; } 简答题 5分

33、阅读下列算法并回答问题： （1）设数组L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f33(L,8)之后的L[1..8]中的元素值； （2）简述函数f33的功能。 void f33(int R[], int n) { int x=R[1]; int low=1, high=n; while(lowhigh) { R[low++]=R[high]; while (low 简答题 5分

34、假设以二叉链表作为二叉树的存储结构，其结点结构为：依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中，参数level为函数执行过程中T当前所指结点的层次，其初值为1；*lmin与*lmax分别为叶子结点的最小层次与最大层次，它们的初值均为０。void f34(BinTree T, int level, int * lmin, int * lmax); 简答题 10分