一． 选择题
1. c语言版数据结构中自定义结构通常用……………………………… （ ）
A、结构体 B、 共同体 C、变量 D、类
2. 算法分析的目的是（ C ）。
A．出数据结构的合理性 B．分析算法的效率以求改进
C．研究算法中的输入和输出的关系 D．分析算法的易懂性和文档性
3. 以下说法错误的是（ C ）。
A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B．在三叉链表上，二叉树的求双亲操作很容易实现
C．在二叉链表上，求双亲操作的时间性能很好
D．在二叉链表上，求根以及求左、右孩子等操作很容易实现
4. 将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（ D ）。
A．20 B．11 C．41 D．10
5. 设指针P指向双链表的某一结点，则双链表结构的对称性可用（ C ）式来刻画。
A．p->prior->next==p->next-> prior； B．p->prior->prior==p->next-> prior；
C．p->next->next==p->prior->prior； D． p->prior->next==p->next->next；
6. 设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为（ B ）个。
A．k+1 B．2k - 1 C．2k D．2k+1
7. 一个栈的入栈序列是a，b，c，d，e，则栈的不可能输出序列（ C ）。
A．e，d，c，b，a B．d，e，c，b，a
C．d，c，e，a，b D．a，b，c，d，e
8. 设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有（ D ）个结点。
A．n1 - 1 B．n1 C．n1 + n2 + n3 D．n2 + n3 + n4
9. 从栈顶指针为Top的链栈中删除一个结点，并将被删结点的值保存到x中其操作步骤为（ A ）。
A．x=Top->data;Top=Top->next; B．Top=Top->next; x=Top->data;
C．x=Top; Top=Top->next; D．x=Top->data;
10. n个结点的线索二叉树中的线索数目为（ C ）。
A．（n-1）个 B．(n+1)个 C．n个 D．(n+2)个
11. 设串S1=‘ABCDEFG’，S2=‘PQRST’，函数StringConcat(X，Y)返回X和Y串的连接串，SubString(S，I，J)返回串S中从序号I的字符开始的J个字符组成的子串，StringLength(S)返回串S的长度，则StringConcat(SubString(S1，2，StringLength(S2))，SubString(S1，StringLength(S2)，2))的结果串是（ C ）。
A．‘BCDEF’ B．‘BCDEFG’ C．‘BCDEFEF’ D．‘BCDQRST’
12. 二维数组A[1..10，1..20]采用列序为主序方式存储，每个数据元素占1个存储单元，且A[1，1]的存储地址是200，则A[6，12]的存储地址是（ ）。
A．317 B．730 C．313 D．315
13. 将长度为n 的单链表接在长度为m的单链表之后的算法的时间复杂度为（C ）
A、O(1) B、O(n) C、O(m) D、O(m+n)
二． 填空题
1. 设n为正数，试确定以下程序段中前面加@的语句的频度：
k=0
for (i=1,i<=n;i++)
for(j=i;j<=n;j++)
@k++
2. 常见时间复杂度的量级有：常数阶O（ ）、对数阶O（ ）、线性阶O（ ）、平方阶O（ ）和指数阶O（ ）。通常认为，具有指数阶量级的算法是 不可行 的。
3. 具有100个结点的完全二叉树的深度是 7 。
4. 设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有 59 个结点。
5. 假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXXX之后，得到的输出序列为 。
6. 设有一个空栈，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push，后栈顶指针所指元素是 。
7. 已知广义表LS=（a，（b，c，d），c），运用GetHead和GetTail函数取出原子d的运算过程为 。
三． 应用题
1. 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首链表的首结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首结点进行统一的管理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。
2. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。
A
/ \
B F
\ \
C G
/\ /
D E H
/ \
B F
\ \
C G
/\ /
D E H
四．算法设计题
1. 设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点 之前 的算法。
2. 编写 递归 算法，对于二叉树中每一个元素值为数据结构与算法题库x的结点，删除以它为根的子树，并释放相应的空间。
五．程序设计（2*6分）
1. 写一个程序，读入500个字符的英语短文，分别统计‘ab’和‘cd’字符串出现的次数。
2. 编一程序为MTV业余歌手统计分数。从键盘读入10个数，去掉一个最高分，去掉一个最低分，求平均值。
1 void main()
2 {
3 float score[10], sumScore, minScore, maxScore;
4 int i, j;
5 for (i = 0; i < 10 ;i ++)
6 {
7 printf("please input %d score\n", i + 1);
8 scanf("%f", &score[i]);
9 }
10 sumScore = minScore = maxScore = score[0];
11 for (j = 1; j < 10; j ++)
12 {
13 if (score[j] > maxScore)
14 {
15 maxScore = score[j];
16 }
17 else if (score[j] < minScore)
18 {
19 minScore = score[j];
20 }
21 sumScore += score[j];
22 }
23 sumScore -= maxScore;
24 sumScore -= minScore;
25
26 printf("the average is %f\n", sumScore/8);
27 }
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论