数据结构与算法的习题.doc

文档介绍：数据结构与算法的习题
一、单项选择题 ：（本大题共20小题，每题 2 分，共 30 分）
（说明：将答案写在试卷后面的答题纸上）
分数
评卷人
、存储和加工处理的对象被统称为( )
A
（11）有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是 。
（12）如果一个图中有n条边，则此图的生成树含有 条边，所以生成树是图的边数 最少 的连通图
（13）由权值为1，2，3，4，5，6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 。
（14）在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为 ，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为 。
（15）树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和
。
（16）无向图的邻接矩阵是 的，并且主对角线上的元素的值为 。
（17）在结点数目相同的二叉树中， 的路径长度最短。
（18）栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表 和 运算的限定不一样。
，算法执行时间T(n)的数量级被称为算法的____时间复杂度____。
。
sum=1；
for（i=0；sum<n;i++）
sum+=1；
：
typedef struct node{
char data［16］；
struct node *next;
} LinkStrNode；
如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。
，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为___________。
。
{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。
，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。
。
，每个结点中最多包含___________个关键字。
，数据元素所占的存储量和整个结点所占的存储量之比称作________。
date
next
栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为________和________。
；空格串的长度是________。
，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。
得分
评卷人
复查人
三、名词解释（本大题共4小题，每小题3分，共12分）
（1）栈：。
（2）树：。
（3）森林：。
（4）满二叉树：。
（5）数据：。
（6）数据对象：。
（7）数据结构：。
（8）算法：
得分
评卷人
复查人
四、简答题（本大题共4小题，每小题5分，共20分）
（1）简述算法的五个重要特性
（2）算法设计的基本要求
（3）试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别
（4）简述二叉树的特点
（5）已知一棵度为k的树中有个度为1的结点，个度为2的结点，。。。个度为k的结点，问该树中有多少个叶子节点？
（7）写出下列树的先根序列和后根序列
（8）已知如图所示的有向图，请给出该图的：
每个顶点的入/出度
邻接矩阵
答案：
得分
评卷人
复查人
五、程序阅读题（本大题共4小题，每小题5分，共20分）
（1）简述以下算法的功能：
status A (linkedlist L)
{
if (L&&L->next)
{Q=L;L=L->next;P=L;
while(P->next) P=P->next;
P-