数据结构试题及答案.docx

.

《数据构造》自考复习思考试题○10

一、单项选择题(本大题共15小题，每题2分，共30分)

在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。

假设将数据构造形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上

( )

操作的有限集合

C.类型的有限集合

B.映象的有限集合

D.关系的有限集合

在长度为n的挨次表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )

n-i+1

C.i+1

B.i

D.n-i

假设不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )

head==NULL

C.head!=NULL

B.head-next==NULL

D.head-next==head

引起循环队列队头位置发生变化的操作是( )

出队 B.入队

C.取队头元素 D.取队尾元素

假设进栈序列为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

字符串通常承受的两种存储方式是( )

散列存储和索引存储 B.索引存储和链式存储

C.挨次存储和链式存储 D.散列存储和挨次存储

设主串长为n，模式串长为m(m≤n)，则在匹配失败状况下，朴实匹配算法进展的无效位移次数为( )

m

C.n-m+1

B.n-m

D.n

二维数组A［12］［18］承受列优先的存储方法，假设每个元素各占3个存储单元，且第1

个元素的地址为150，则元素A［9］［7］的地址为( )

A.429 B.432

.

.

C.435 D.438

对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )

(e,f)

C.(f)

B.((e,f))

D.()

以以下图示的挨次存储构造表示的二叉树是( )

n个顶点的强连通图中至少含有( )

A.n-1条有向边

C.n(n-1)/2条有向边

B.n条有向边

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)

假设在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为

( )

A.4 B.5

C.8 D.9

由同一关键字集合构造的各棵二叉排序树( )

其形态不愿定一样，但平均查找长度一样

其形态不愿定一样，平均查找长度也不愿定一样

其形态均一样，但平均查找长度不愿定一样

.

.

其形态均一样，平均查找长度也都一样

ISAM文件和VSAM文件的区分之一是( )

前者是索引挨次文件，后者是索引非挨次文件

前者只能进展挨次存取，后者只能进展随机存取

前者建立静态索引构造，后者建立动态索引构造

前者的存储介质是磁盘，后者的存储介质不是磁盘

二、填空题(本大题共10小题，每空2分，共20分)

数据的规律构造在计算机存储器内的表示，称为数据的 。

删除双向循环链表中*p的前驱结点(存在)应执行的语句是 。

栈下溢是指在 时进展出栈操作。

substr(s,i,len)函数的功能是返回串s中第i个字符开头长度为len的子串，strlen(s)函数的功能是返回串s的长度。假设s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t),strlen(t))后的返回值为 。

去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的

。

完全二叉树T的第5层只有7个结点，则该树共有 个叶子结点。

在有向图中，以顶点v为终点的边的数目称为v的 。

当关键字的取值范围是实数集合时，无法进展箱排序和 排序。

产生冲突现象的两个关键字称为该散列函数的 。

假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入的记录时，该桶中 。

三、解答题(本大题共4小题，每题5分，共20分)

假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。

(1)写出队满的条件表达式；(