一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( )
A. 操作的有限集合 B. 映象的有限集合
C. 类型的有限集合 D. 关系的有限集合
2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )
A. n-i+1 B. i
C. i+1 D. n-i
3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )
A. head==NULL B. head->next==NULL
C. head!=NULL D. head->next==head
4. 引起循环队列队头位置发生变化的操作是( )
A. 出队 B. 入队
C. 取队头元素 D. 取队尾元素
5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )
A. 2，4，3，1，5，6 B. 3，2，4，1，6，5
C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
6. 字符串通常采用的两种存储方式是( )
A. 散列存储和索引存储 B. 索引存储和链式存储
C. 顺序存储和链式存储 D. 散列存储和顺序存储
7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为( )
A. m B. n-m
C. n-m+1 D. n
8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( )
A. 429 B. 432
C. 435 D. 438
9. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )
A. (e,f) B. ((e,f))
C. (f) D. ( )
10. 下列图示的顺序存储结构表示的二叉树是( )
11. n个顶点的强连通图中至少含有( )
A. n-1条有向边 B. n条有向边
C. n(n-1)/2条有向边 D. n(n-1)条有向边
12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为 ( )
A. (19，23，56，34，78，67，88，92) B. 23，56，78，66，88，92，19，34)
C. (19，23，34，56，67，78，88，92) D. (19，23，67，56，34，78，92，88)
13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )
A. 4 B. 5
C. 8 D. 9
14. 由同一关键字集合构造的各棵二叉排序树( )
A. 其形态不一定相同，但平均查找长度相同
B. 其形态不一定相同，平均查找长度也不一定相同
C. 其形态均相同，但平均查找长度不一定相同
D. 其形态均相同，平均查找长度也都相同
15. ISAM文件和VSAM文件的区别之一是( )
A. 前者是索引顺序文件，后者是索引非顺序文件
B. 前者只能进行顺序存取，后者只能进行随机存取
C. 前者建立静态索引结构，后者建立动态索引结构
D. 前者的存储介质是磁盘，后者的存储介质不是磁盘
二、填空题(本大题共10小题，每空2分，共20分)
16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。
17. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。
18. 栈下溢是指在____________时进行出栈操作。
19. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。
20. 去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的____________。
21. 已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。
22. 在有向图中，以顶点v为终点的边的数目称为v的____________。
23. 当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。
24. 产生冲突现象的两个关键字称为该散列函数的____________。
25. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( )
A. 操作的有限集合 B. 映象的有限集合
C. 类型的有限集合 D. 关系的有限集合
2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )
A. n-i+1 B. i
C. i+1 D. n-i
3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )
A. head==NULL B. head->next==NULL
C. head!=NULL D. head->next==head
4. 引起循环队列队头位置发生变化的操作是( )
A. 出队 B. 入队
C. 取队头元素 D. 取队尾元素
5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )
A. 2，4，3，1，5，6 B. 3，2，4，1，6，5
C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
6. 字符串通常采用的两种存储方式是( )
A. 散列存储和索引存储 B. 索引存储和链式存储
C. 顺序存储和链式存储 D. 散列存储和顺序存储
7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为( )
A. m B. n-m
C. n-m+1 D. n
8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( )
A. 429 B. 432
C. 435 D. 438
9. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )
A. (e,f) B. ((e,f))
C. (f) D. ( )
10. 下列图示的顺序存储结构表示的二叉树是( )
11. n个顶点的强连通图中至少含有( )
A. n-1条有向边 B. n条有向边
C. n(n-1)/2条有向边 D. n(n-1)条有向边
12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为 ( )
A. (19，23，56，34，78，67，88，92) B. 23，56，78，66，88，92，19，34)
C. (19，23，34，56，67，78，88，92) D. (19，23，67，56，34，78，92，88)
13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )
A. 4 B. 5
C. 8 D. 9
14. 由同一关键字集合构造的各棵二叉排序树( )
A. 其形态不一定相同，但平均查找长度相同
B. 其形态不一定相同，平均查找长度也不一定相同
C. 其形态均相同，但平均查找长度不一定相同
D. 其形态均相同，平均查找长度也都相同
15. ISAM文件和VSAM文件的区别之一是( )
A. 前者是索引顺序文件，后者是索引非顺序文件
B. 前者只能进行顺序存取，后者只能进行随机存取
C. 前者建立静态索引结构，后者建立动态索引结构
D. 前者的存储介质是磁盘，后者的存储介质不是磁盘
二、填空题(本大题共10小题，每空2分，共20分)
16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。
17. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。
18. 栈下溢是指在____________时进行出栈操作。
19. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。
20. 去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的____________。
21. 已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。
22. 在有向图中，以顶点v为终点的边的数目称为v的____________。
23. 当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。
24. 产生冲突现象的两个关键字称为该散列函数的____________。
25. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。
