数据结构与算法分析 复习题
- 格式：doc
- 大小：28.50 KB
- 文档页数：2
第 1 页/共 2 页 《数据结构与算法分析》2012～2013学年第二学期
复习题
一、选择题
1．算法分析的目的是（ ）：
A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性
2. 在数据结构中，逻辑上数据结构可分为________。
A．动态结构和静态结构 B．线性结构和非线性结构
C．紧凑结构和非紧凑结构 D．内部结构和外部结构
3．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。
A.正确 B.不正确
4．在一个单链表中，若删除p所指结点的后续结点，则执行：
A. p->next=p->next->next B. p->next=p->next C. p= p->next->next D. p= p->next
5．从表中任一结点出发，都能扫描整个表的是（ ）。
A. 单链表 B. 顺序表 C. 循环链表 D. 静态链表
6．在一棵具有5层的满二叉树中结点总数为（ ）。
A. 31 B. 32 C. 33 D. 16
7．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A. 完全图 B. 连通图 C. 有回路 D. 一棵树
8．无向图的邻接矩阵是一个（ ）。
A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵
9．下列排序方法中（ ）方法是不稳定的。
A. 冒泡排序 B. 选择排序 C. 堆排序 D. 直接插入排序
10．判断一个循环队列Q（最多n个元素）为满的条件是（ ）。
A. Q->rear==Q->front B. Q->rear==Q->front+1
C. Q->front=(Q->rear+1)%n D. Q->front==(Q->rear-1)%n
二、填空题
1、对稀疏矩阵进行压缩存储，常用的两种方法： ① 和 ② 。
2、若对二叉排序树进行遍历，保证输出的所有结点序列按键值递增排序，对二叉排序树应进行 ③ 遍历。
3、队列的特点是 ④ ，栈的特点是 ⑤ 。
4、树内各结点度的 ⑥ 称为树的度。
5、一个图的 ⑦ 表示法是惟一的。
6、在散列函数H(key)=key％p中，p应取 ⑧ 。
7、具有相同函数值的关键字对哈希函数来说称为 ⑨ 。
8、数据结构的四种基本类型中， ⑩ 的元素是一对多关系。
三、判断题
1．采用压缩存储之后，下三角矩阵的存储空间可以节约将近一半。 （ ）
2．广义表的元素可以是子表，也可以是单元素。 （ ）
3．树的后序遍历与其对应的二叉树的后序遍历序列相同。 （ ）
4．在具有头结点的单链表中，头指针指向链表的第一个数据结点。 （ ）
5．链式存储的线性表可以随机存取。 （ ）
6．以链表作为栈的存储结构，出栈操作必须判别栈空的情况。 （ ）
7．图的深度优先搜索序列和广度优先搜索序列不是惟一的。 （ ）
8．二叉树的先序遍历中，任意结点均处在其子女结点之前。 （ ）
9．快速排序在所有排序方法中最快，而且所需附加空间也最少。 （ ）
四、分析题
1、设ｎ为正整数，试确定如下程序段中语句“x++;”的频度。
for (i=1;i<=n;i++)
for (j=i;j<=n;j++)
for (k=1;k<=n;k++)
x++;
第 2 页/共 2 页 2、线性表的元素类型定义如下：
struct node {int data;
struct node *next;
};
typedef struct node NODE;
请分析下列函数的功能。
NODE *operation (NODE *h, int x)
{ NODE *p;
p=h;
while (p!=NULL && p->data!=x)
p=p->next;
return (p);
}
3、设二叉树的元素类型定义如下：
struct node {int data;
struct node *lc;
struct node *rc;
};
typedef struct node NODE;
请分析下列函数的功能。
void operation (NODE *r)
{ int i=0;
NODE *p, * s[MAX];
p=r;
do{while (p!=NULL)
{s[i++]=p;p=p->lc;}
if (i>0)
{ p=s[--i];
printf(“%d\n”,p->data);
p=p->rc;}
}while (i>0||p!=NULL);
}
4、一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，建立一棵huffman树。
5、假设某二叉树的先序遍历序列为：ABDGJEHCFIKL，中序遍历序列为：DJGBEHACKILF，试绘出该二叉树。
五、算法设计题
1．试编写一个算法，计算不带头结点的单链表的长度。
2．已知某二叉树的结点定义如下：
typedef int datatype;
typedef struct node {
datatype data;
Struct node *lchild, *rchild;
} BiTree;
试编写递归算法，计算此二叉树中叶子结点的个数。
int CountNode(BiTree *T)
{
}
![数据结构c语言版期末考试复习试题[1]](https://imgs-1438308264.cos.ap-hongkong.myqcloud.com/85c65a2f2e60ddccda38376baf1ffc4ffe47e2f2.webp)