1、若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上（ ） 单选题 2分

2、在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为 【 】 单选题 2分

3、若不带头结点的单链表的头指针为head，则该链表为空的判定条件是 【 】 单选题 2分

4、引起循环队列队头位置发生变化的操作是 【 】 单选题 2分

5、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 【 】 单选题 2分

6、字符串通常采用的两种存储方式是 【 】 单选题 2分

7、设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 【 】 单选题 2分

8、二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为 【 】 单选题 2分

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

10、 单选题 2分

11、n个顶点的强连通图中至少含有 【 】 单选题 2分

12、对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为 【 】 单选题 2分

13、若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（ ） 单选题 2分

14、由同一关键字集合构造的各棵二叉排序树 【 】 单选题 2分

15、ISAM文件和VSAM文件的区别之一是 【 】 单选题 2分

16、数据的逻辑结构在计算机存储器内的表示，称为数据的（ ）。 填空题 2分

17、删除双向循环链表中*p的前驱结点(存在)应执行的语句是（ ）。 填空题 2分

18、栈下溢是指在（ ）时进行出栈操作。 填空题 2分

19、已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为（ ）。 填空题 2分

20、去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的（ ）。 填空题 2分

21、已知完全二叉树T的第5层只有7个结点，则该树共有（ ）个叶子结点。 填空题 2分

22、在有向图中，以顶点v为终点的边的数目称为v的（ ）。 填空题 2分

23、当关键字的取值范围是实数集合时，无法进行箱排序和（ ）排序。 填空题 2分

24、产生冲突现象的两个关键字称为该散列函数的（ ）。 填空题 2分

25、假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中（ ）。 填空题 2分

26、假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式；(3)设m=40,rear=13,quelen=19,求队头元素的位置；(4)写出一般情况下队头元素位置的表达式。 简答题 5分

27、已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。 简答题 5分

28、画出下图所示有向图的所有强连通分量。 简答题 5分

29、对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；(2)对所举序列进行快速排序，写出排序过程。 简答题 5分

30、阅读下列算法，并回答问题： (1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L； (2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L； (3)简述算法的功能。 void f30(SeqList*L, DataType x) { int i =0, j; while (ilength && x>L->data［i］)i++; if(ilength && x==L->data［i］) { for(j=i+1;jlength;j++) L->data［j-1］=L->data［j］; L->length--; } else { for(j=L->length;j>i;j--) L->data［j］=L->data［j-1］; L->data［i］=x; L->length++; } } 简答题 5分

31、已知图的邻接表表示的形式说明如下： #define MaxNum 50 //图的最大顶点数 typedef struct node { int adjvex; //邻接点域 struct node *next; //链指针域 } EdgeNode; //边表结点结构描述 typedef struct { char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct { VertexNode adjlist［MaxNum］; //邻接表 int n, e; //图中当前的顶点数和边数 } ALGraph; //邻接表结构描述 下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 typedef enum {FALSE, TRUE} Boolean; Boolean visited［MaxNum］; void DFSForest(ALGraph *G){ int i; for(i=0;in;i++) visited［i］= (1) ; for(i=0;in;i++) if (!visited［i］) DFSTree(G,i); } void DFSTree(ALGraph *G, int i) { EdgeNode *p; visited［i］=TRUE; p=G->adjlist［i］. firstedge; while(p!=NULL){ if(!visited［p->adjvex］){ printf(″″,G->adjlist［i］. vertex, G->adjlist［p->adjvex］. vertex); (2) ; } (3) ; } } 简答题 5分

32、阅读下列算法，并回答问题： (1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L； (2)写出上述函数调用过程中进行元素交换操作的总次数。 void f32(int R［］,int n){ int i,t; for (i=0;i 简答题 5分

33、已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。 void f33 (LinkList L, LinkList H［］, int m) {//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for (i=0;inext; while(p) { q=p->next; j=p->key%m; (2) ; H［j］=p; (3) ; } free(L); } 简答题 5分

34、假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：typedef char DataType;typedef struct node {     DataType data;     struct node *lchild, *rchild;       //左右孩子指针     struct node *parent;             //指向双亲的指针} BinTNode;typedef BinTNode *BinTree;若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。(1)就后继的不同情况，简要叙述实现求后继操作的方法；(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。 简答题 10分