数据结构题目及答案(2)

35 17 8 4 2 1 0

余数 1 1 0 0 1

结果：10011

图3-1 十进制数转换成二进制数的过程

由题意可知，我们可以用一个栈来保存所有的余数，当商为0时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下：

void conversion(){ Stack S; int n; InitStack(&S);

printf(\scanf(\ if(n<0){

printf(\ return; }

if(n==0) Push(S,0); while(n!=0){

Push(S,n%2); n=n/2; }

printf(\ while(!StackEmpty(*S)){

printf(\} } }

6

第四章 串

单项选择题

1．串是一种特殊的线性表，其特殊性体现在 B 。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符

2．设有两个串p和q，求q在p中首次出现的位置的运算称作 B 。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 3．串是一个 B 的序列。

A. 不少于一个字母 B. 有限个字符 C. 不少于一个字符 D. 空格或字母 4．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为 D 。 A. 8 B. 9 C. 36 D. 37 填空题

1．两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。 2．空格串是 由一个或多个空格字符组成的串 ,其长度等于 其包含的空格个数 。 3．在串S=’tuition’中，以t为首字符且值不相同的子串有 10 个。

4. 使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2)的串操作，可从串s=’conduction’中的字符得到串t=’cont’，则求t的串表达式为 concat(subString(s,1,3),substring(s,7,1)) 。

第五章 数组与广义表

单项选择题

1．常对数组进行的两种操作是 C 。

A. 建立与删除 B. 索引和修改 C. 查找和修改 D. 查找与索引 2．假设8行10列的二维数组a[1..8, 1..10]分别以行序为主序和以列序为主序顺序存储时，

其首地址相同，那么以行序为主序时元素a[3][5]的地址与以列序为主序时元素 ____ D ___的地址相同。

A. a[5][3] B. a[8][3] C. a[1][4] D. 答案A、B、C均不对 3．将一个A[1..100,1..100]的三对角矩阵以行序为主序存入一维数组B[1..298]中，元素A[66，65]在B数组中的位置k等于____ D ___。 A. 198 B. 197 C. 196 D. 195

4．稀疏矩阵一般的压缩存储方法有两种，即 C 。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 5. 一个非空广义表的表头____ D ___。

7

A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是原子或子表 6. 设head(L)、tail(L)分别为取广义表表头、表尾操作，则从广义表L=((x,y,z),a,(u,v,w))中取出原子u的运算为____ D ___。

A. head(tail(tail(head(L)))) B. tail(head(head(tail(L)))) C. head(tail(head(tail(L)))) D. head(head(tail(tail(L)))) 7．广义表(a,((b,(c,d,(e,f))),g))的深度为____ C ___。 A. 3 B. 4 C. 5 D. 6 填空题

1．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占四个单元，则元素A[7,5]的地址为 1100 。

2．二维数组A[0..9,0..19]采用行序为主方式存储，每个元素占一个存储单元，并且元素A[0,0]的存储地址是200，则元素A[6,12]的地址是 332 。

3．二维数组A[10..20,5..10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10,5]的存储地址是1000，则元素A[18,9]的地址是 1208 。

4．有一个10阶对称矩阵A，采用压缩存储方式（以行序为主序存储，且元素A[0,0]地址为1），则元素A[8,5]的地址是 42 。

5．设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[] 是函数的符号，给出下列广义表的运算结果： HEAD[(a，b，c)]的结果是 ① 。 TAIL[(a，b，c)]的结果是 ② 。 HEAD[((a)，(b))]的结果是 ③ 。 TAIL[((a)，(b))]的结果是 ④ 。 HEAD[TAIL[(a，b，c)]的结果是 ⑤ 。 TAIL[HEAD((a，b)，(c，d))]的结果是 ⑥ 。 HEAD[HEAD[(a，b)，(c，d))]]的结果是 ⑦ 。 TAIL[TAIL[(a，(c，d))]]的结果是 ⑧ 。

①a；②(b，c)；③(a)；④((b))；⑤b；⑥(b)；⑦a；⑧( )

第6章 树和二叉树

选择题

1． 以下说法错误的是 A 。

A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种\分支层次\结构

8

2. 如图6-2所示的 4 棵二叉树中， C 不是完全二叉树。

图6-2 4 棵二叉树

3. 以下说法错误的是 D 。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好

4. 如图6-3所示的 4 棵二叉树， B 是平衡二叉树。

图6-3 4 棵二叉树

5. 如图6-4所示二叉树的中序遍历序列是 B 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc

abcdgef

图6-4 1 棵二叉树

6. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是dgbaechf，

9

则其后序遍历的结点访问顺序是 D 。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

7. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为 D 。 A.42 B.40 C.21 D.20

8. 一棵二叉树如图6-5所示，其后序遍历的序列为 C 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh

abcdefgh 图6-5 1 棵二叉树

9. 深度为 5 的二叉树至多有 C 个结点。 A. 16 B. 32 C.31 D.10

10. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数至少有 C 个。

A.k+1 B.2k C.2k-1 D.2k+1

11. 对含有 B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A.0 B.1 C.2 D.不存在这样的二叉树 填空题

1. 有一棵树如图6-7 所示，回答下面的问题：

k1k2k3k4k5k6k7 图6-7 1 棵二叉树

（1）这棵树的根结点是 ① ；

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题目及答案(2)在线全文阅读。