数据结构试卷及答案压缩版
《数据结构》试卷及答案
1．算法分析的目的是( )。
A.找出数据结构的合理性
B.研究算法中输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易懂性和文档性
2．（）是具有相同特性数据元素的集合，是数据的子集。
A.数据符号
B.数据对象
C.数据
D.数据结构
3．用链表表示线性表的优点是( )。
A.便于随机存取
B.花费的存储空间比顺序表少
C.便于插入与删除
D.数据元素的物理顺序与逻辑顺序相同
4．输入序列为（A,B,C,D）不可能的输出有（）。
A.(A,B,C,D)
B. (D,C,B,A)
C. (A,C,D,B) D . (C,A,B,D)
5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。
A. front=maxSize
B. (rear+1)%maxSize=front
C. rear=maxSize
D. rear=front
6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。
A. student
B. a good s
C. good
D. a good
7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。
A.23
B.33
C.18
D. 40
8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。
A. Gethead(Gethead(LS))
B. Gettail(Gethead(LS))
C. Gethead(Gethead(Gettail(LS)))
D. Gethead(Gettail(LS))
9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( )
A. CDBGFEA
B. CDBFGEA
C. CDBAGFE
D. BCDAGFE
10．下列存储形式中，( ) 不是树的存储形式。
A.双亲表示法
B.左子女右兄弟表示法
C.广义表表示法
D.顺序表示法
11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。
A.直接选择排序
B.直接插入排序
C.快速排序
D.起泡排序
12．采用折半查找方法进行查找，数据文件应为（），且限于（）。
A.有序表顺序存储结构
B.有序表链式存储结构
C.随机表顺序存储结构
D.随机表链式存储结构
13．就平均查找速度而言，下列几种查找速度从慢至快的关系是（）
A.顺序折半哈希分块
B.顺序分块折半哈希
C.分块折半哈希顺序
D.顺序哈希分块折半
14．执行下面程序段时，执行S语句的次数为（）
for(int I=1;I<=n;I++)
for(int j=1;j<=I;j++)
S;
A. n2
B. n2/2
C. n(n+1)
D. n(n+1)/2
15．串是一种特殊的线性表，其特殊性体现在（）
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
D.数据元素可以是多个字符
16．树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论( )是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
17．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为( )。
A. 60
B. 66
C. 67
D. 50
18．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个
A. 33
B. 34
C. 32
D. 30
19．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时，（）次比较后查找成功。
A. 1
B. 2
C. 4
D. 8
20．若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，以下为二路归并排序过程。第二趟为:
A.[265 301] [129 751] [863 937] [694 742] [076 438]
B.[076 129 265 301 438 694 742 751 863 937]
C.[129 265 301 694 742 751 863 937] [076 438]
D.[129 265 301 751] [694 742 863 937] [076 438]
二、填空题（本大题共6小题，每空2分，共12分；答案填在下表内）
1 算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是_______ 、______ 、________ 、有零或多个输入和有一或多个输出。
2 算法优劣的五个标准是正确性、可使用性、______、______、_____。
3 有n个球队参加的足球联赛按主客场制进行比赛，共需进行_________场比赛。
4 设有串t='I am a student '，s='good'，那么Concat(t,s)= 'I am a student good'，Substr(t,8,7)= __________。
5 在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_________ 结构，其主要特点是__________。
6 广义表((a),a)的表头是_______，表尾是_______。
三、判断题（对的打“√”，错的打“×”。每小题1分，共10分;答案填在下表内）
1数据的逻辑结构与数据元素本身的内容和形式无关。
2 三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。
3中序序列和后序序列相同的二叉树为：空树和缺右子树的单支树。
4对于两棵具有相同关键字集合而形状不同的二叉排序树，中序遍历后得到的关键字排列顺序相同。
5 序列{30，40，50，15，25，35，38，10}是堆。
6 对于无向图的生成树，从同一顶点出发所得的生成树相同。
7 若设哈希表长m=14，哈希函数H(key)=key%11，表中已有4个结点。addr(15)=4
addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是9。
8一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号则，则编号最小的叶子的序号是2k-2+1 ；编号是i的结点所在的层次号是「log2 i|+1。（「log2 i|表示向上取整」（根所在的层次号规定为1层）。
9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。
10算法可以没有输入，但是必须有输出。
四、画出树的孩子兄弟表示法示意的树或森林。（4分）
设关键字的输入序列为{4，5，7，2，1，3，6}
1．（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。
2.（4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列
六、按要求做题（本大题共2小题，共12分）
（5分）
七、算法分析设计题（本大题共5小题，共30分）
1．写出程序段的功能,并给出一个测试用例（一个输入数据和一个输出结果）(5分)。void conversion()
{
Stack s;
int n;
SElemType e;
initstack(s);
printf("Please input number:");
scanf(“%d”,&n);
while(n)
{push(s,n%8);
n=n/8;
}
while(!stackempty(s))
{pop(s,e);
printf(“%d”,e);
}
}
2.下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数,请在标号处填写
合适的语句。(每空1分，共5分)
程序:
Void preorder(bitree *T)
{bitree *stack[m];
int top;
if(T!=NULL)
{top=1;
stack[top]=(1);
while( (2) )
{p=stack[top];
top--;
printf(“%d”,p->data);
if(p->rchild!=NULL){ (3) ; stack[top]=p->rchild;}
if( (4) ) { top++; (5) ;}
}
}
}
⑴⑵⑶
⑷⑸
3.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分)
int Binary_Search(S_TBL tbl，KEY kx)
{ /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0 */ int mid，flag=0；
low=1；high=length；
while( ⑴&!flag )
{ /* 非空，进行比较测试*/
mid= ⑵；
if(kx else if(kx>tbl.elem[mid].key) ⑷； else { flag= ⑸；break；} } return flag; } ⑴⑵⑶ ⑷⑸ 4.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分) 程序： Void seletesort(int A[n],int n) { int i,j,t,minval,minidx; for(i=1;i<=n-1;i++) { minval=A[i+1]; (1) for(j=i+2;j<=n;j++) if( (2) ) { (3) ; minidx=j;} if( (4) ) {t=A[i+1]; (5) A[minidx]=t; } } } ⑴⑵⑶ ⑷⑸ 5 试写出求有向无环图的关键路径算法的设计思路（10分） 数据结构试卷A答案 选择题（本大题共20小题，每题1分，共20分；答案填在下表内） 二、填空题（本大题共5小题，每空1分，共12分；答案填在下表内） 1 有穷性确定性可行性 2 可读性健壮性效率 3 n(n-1) 4 'student' 5 队列 先进先出 6 (a) (a) 三、判断题（对的打“√” 1）true ; 2 ）flase; 3）true; 46）flase ; 7）true; 8）true; 9 其他形式的树形结构酌情给分。 五、要求题（本大题共2小题，共121 2.一趟划分后的数据序列 六、按要求做题（12分） 1 DFS 遍历序列BFS 遍历序列v1 v 2 v 3 v 4 v 5 情扣分。） 2 1.测试用例：输入10 输出 12 2（5分，每空1分）（1）T (2) top>0 (3) top++ (4) p->lchild!=NULL (5) stack[top]=p->lchild 3 （5分，每空1分） （1）low<=high (2) (low+high)/2 (3) high=mid-1 (4) low=mid+1 (5) 1 4.（5分，每空1分） （1）minidx=i+1 (2) minval>A[j] (3) minval=A[j] (4) i!=j (5) A[i+1]=A[minidx] 5（10分，不同答案，酌情得分） 输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序 排序过程中求顶点的Ve[i] 将得到的拓扑序列进栈 按逆拓扑序列求顶点的Vl[i] 计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动 第 2 学期数据结构试卷A 一、选择题（本大题共15小题，每题2分，共30分；答案填在下表内） 1.从一个长度为100的顺序表中删除第30个元素时需向前移动个元素 A、70 B、71 C、69 D、30 2.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为______。 A、 top不变 B、top=0 C、top=top-1 D、top=top+1 3.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功情况下,则平均比较____个结点。 A、n B、n/2 C、(n-1)/2 D、(n+1)/2 4.在一个单链表中,若要删除p指针所指结点的后继结点,则执行 A、p-> next; p-> next=p-> next-> next; B、p-> next=p-> next-> next; C、p=p-> next; D、p=p-> next->>next; 5.在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行___。 A、front-> next=s； front=s； B、s-> next=rear; rear=s； C、rear-> next=s; rear=s； D、s-> next=front; front=s； 6.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结点数为1个,那么度为0的结点数为____个 A、6 B、7 C、 8 D、9 7.假定一棵二叉树的结点数为33个,则它的最小高度为__,最大高度为___ A、 4,33 B、5,33 C、6,33 D、6,32 8. 在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为___。 A、2i B、2i+1 C、2i-1 D、i/2 9.在一个有向图中,所有顶点的入度之和等于所有弧数和___倍。 A、1 B、2 C、3 D、4 10.对于一个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为___。 A、 N B、(N-1)2 C、(N+1)2 D、 N2 11.已知一个图如图所示，在该图的最小生成树中各边上数值之和为____。 A、21 B、26 C、28 D、33 12.已知一个图如图所示，由该图行到的一种拓朴序列为 A、v1 v4 v6 v2 v5 v3 B、v1 v2 v3 v4 v5 v6 C、v1 v4 v2 v3 v6 v5 D、v1 v2 v4 v6 v3 v5 13.二维数组M 的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到4，列下标j 的范围从0到5，M 按行存储时元素M[2][4]的起始地址与M 按列存储时元素 的起始地址相同。 A 、m[2][4] B 、M[4][2] C 、M[3][1] D 、M[3][1] 14.具有6个结点的无向图至少应有 条边才能保证是连通图。 A 、 5 B 、 6 C 、 7 D 、 8 15.采用邻接表存储的图的深度优先遍历类似于二叉树的 。 A 先序遍历 B 中序遍历 C. 后序遍历 D. 按层遍历 二、填空题（本大题共5小题，每空1分，共8分；答案填在下表内） 根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、（1） 和 （2） 。 2.评价算法的标准很多，通常是以执行算法所需要的 （3） 和所占用的（4） 来判别一个算法的优劣。 3.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的（5） 也是相邻的。 4.空格串的长度为串中所包含 （6） 字符的个数，空串的长度为 （7） 5.加上表示指向前驱和 （8） 的线索的二叉数称为线索二叉树。 三、判断题（对的打“√”，错的打“×”。每小题1分，共10分） （ ）1.线性表的唯一存储形式是链表。 （ ）2.已知指针P 指向键表L 中的某结点，执行语句P=P-〉next 不会删除该链表中的结点。 （ ）3.在链队列中，即使不设置尾指针也能进行入队操作。 （ ）4.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。 （ ）5.设与一棵树T 所对应的二叉树为BT ，则与T 中的叶子结点所对应的BT 中的结点也 一定是叶子结点。 （）6.快速排序是不稳定排序。 （）7.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。 （）8.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。 （）9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 （）10.基数排序是多关键字排序。从最低位关键字起进行排序。 四、应用题。（共44分） 1.画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS序列。（12分） 2.假设用于通信的电子由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}画出哈夫曼树，并为这8个字母设计哈夫曼编码。（8分） 3. 已知序列{70，73，69，23，93，18,11，68}请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。（10分） 4.设有一组关键字关键码集为{47，7，29，11，16，92，22，8，3}，哈希表表长为11，Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。（8分） 5. 二叉树的先序遍历序列为 A B C D E F G H I，中序遍历序列为 B C A E D G H F I，画出这棵二叉树。(6分) 五、算法设计题（8分） 定义有序表抽象数据类型，并据此类型设计折半查找算法。 2学期数据结构试卷A参考答案及评分标准 一、选择题本大题共15小题，每题2分，共30分 1.（12分） 011000 101000 100001 010010 000101 001010 DFS 序列2. （8分） 直接插入排序 70，73，69，23，93，18,11，68 [70，73]，69，23，93，18,11，68 [70，69，73]， 23，93，18,11，68 [23,70，69，73]， 93，18,11，68 [23,70，69，73， 93]，18,11，68 [18,23,70，69，73， 93]， 11，68 [11，18,23,70，69，73， 93]， 68 [11，18,23,68,70，69，73， 93] 快速排序 [68,11,69,23,18] ,70,[93,73] 4. （8分） 0 1 2 3 4 5 6 7 8 9 10 5. （6分） 四、算法设计题（8分） typedef struct { int key; float info; }JD; int binsrch(JD r[],int n,int k) { int low,high,mid,found; low=1; high=n; found=0; while((low<=high)&&(found==0)) { mid=(low+high)/2; if(k>r[mid].key) low=mid+1; else if(k==r[mid].key) found=1; else high=mid-1; } if(found==1) return(mid); else return(0); } 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 数据结构实验五矩阵的压缩存储与运算 第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 第二章线性表 一、顺序表和链表的优缺点 1.顺序表 定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素（平均约需移动一半结点，当n很大时，算法的效率较低） 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 2.链式存储结构 定义：由分别表示a1,a2,…,a i-1,a i,…,a n的N 个结点依次相链构成的链表，称为线性表的链式存储表示 优势： (1)能有效利用存储空间； 动态存储分配的结构，不需预先为线性表分配足够大的空间，而是向系统“随用随取”，在删除元素时可同时释放空间。 (2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作； 插入或删除时只需要修改指针，而不需要元素移动。 劣势： (1)不能随机存取数据元素； (2)丢失了一些顺序表的长处，如线性表的“表长”和数据元素在线性表中的 “位序”，在单链表中都看不见了。如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。 二、单链表中删除一个节点和插入一个节点的语句操作，p29 1.插入元素操作 算法基本思想：首先找到相应结点，然后修改相应指针。 假定在a，b之间插入结点X，s指向X, p指向a，指针修改语句为： s->next=p->next; p->next =s; 2.删除元素操作 算法基本思想:首先找到第i-1 个结点，然后修改相应指针。 删除b结点，其中，P指向a，指针修改语句为：p->next=p->next->next； 三、单链表的就地逆置习题集2.22 算法的基本思想：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点）。 算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。 void reverse (Linklist H){ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p){ q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 第三章栈和队列 一、栈和队列的特性 1.特点 栈必须按“后进先出”（LIFO）的规则进行操作，仅限在表尾进行插入和删除的操作。 队列（FIFO）必须按“先进先出”的规则进行操作，队尾插入，队头删除。 二、循环队列为空和满的判定方法，p63 队空条件：front == rear; 队满条件：(rear + 1) % maxSize == front 数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 一、 名词解释 1、数据压缩：以最小的数码表示信源所发的信号，减少容纳给定消息集合或数据采样 集合的信号空间 2、数据压缩比： 将压缩前每个信源符号（取样）的编码位数（m log ）与压缩后平均每符号的编码位数（l ） 之比，定义为数据压缩比 3、均匀量化：把输入信号的取值域按等距离分割的量化称为均匀量化 4、最优量化（MMSE 准则）：使均方误差最小的编码器设计方法称为最小均方误差 （MMSE ）设计。以波形编码器的输入样值k x 与波形解码器的输出样值k y 之差 k k k y x e -=的均方误差{}22k e e E =σ 作为信号质量的客观评判标准和MMSE 的设计准则。 （能使量化误差最小的所谓最佳量化器，应该是非均匀的。） 5、信息熵定义：信息量的概率平均值，即随机变量)(j a I 的数学期望值，叫做信息熵 或者简称熵 6、统计编码定义：主要利用消息或消息序列出现概率的分布特性，注重寻找概率与码 字长度间的最优匹配，叫做统计编码或概率匹配编码，统称熵编码。 7、变长编码： 与等长编码相对应，对一个消息集合中的不同消息，也可以用不同长度 码字来表示，这就叫做不等长编码或变长编码。 8、非续长码： 若W 中任一码字都不是另一个码字的字头，换句换说，任何一个码字 都不是由另一个码字加上若干码元所构成，则W 称为非续长码、异字头码或前缀码。 9、游程长度：是指字符（或信号采样值）构成的数据流中各字符重复出现而形成字符 串的长度 10、电视图像的取向：我国彩色电视制式采用逐行倒相的PAL-D 制。 11、HVS 的时间掩蔽特性：指随着时间变化频率的提高，人眼对细节分辨能力下降的 特性 12、空间掩蔽特性：指随着空间变化频率的提高，人眼对细节分辨能力下降的特性 13、亮度掩蔽特性：指在背景较亮或较暗时，人眼对亮度不敏感的特性 14、CIF 格式：是常用的标准图像格式。是一种规范Y 、B C 、R C 色差分量视频信号 的像素分辨率的标准格式。288352?=CIF 像素。 15、SIF 格式:是一种用于数字视频的存储和传输的视频格式。 16、压扩量化：由于低电平信号出现概率大、量化噪声小；高电平信号虽然量化噪声变 大，但因为出现概率小，总的量化噪声还是变小了，从而提高量化信噪比。这种方法叫做压 缩扩张量化。（压扩量化用一个非线性函数变换先将信号“压缩”后再均匀量化，它和非线 性量化器完全等效。） 17、信号压缩系统的复杂度：指实现编解码算法所需的硬件设备量，典型地可用算法的 运算量及需要的存储量来度量。 18、离散信源：被假设为由一系列随机变量所代表，往往用随机出现的符号表示，称输 出这些符号集的源为信源，如果取值于某一离散集合，就叫做离散信源。 19、互信息量：对两个离散随机时间集X 和Y ，事件j y 的出现给出关于i x 的信息量，即为互信息量。 20、联合熵：两个变量 和 的联合熵定义为：∑∑==-=m j n k k j k j b a P b a P Y X H 11)(log ),()(，即平均互信息量表示信源X 的平均不确定性与 其在信源Y 被确定条件下仍保留的平均不确定性之差。（联合熵是联合概率分布所具有信息 量的概率平均值，表示两个事件集联合发生时所能得到的总的平均信息量。） 21、极限熵：如果把n 个信源符号当作一个n 维随机矢量X 。n 越大，所得到的熵就 越接近于实际信源所含有的熵，而式 ),,,()(121lim lim -∞ →∞→=n n n n n X X X X H X H ，称为极限熵或极限信息量，用∞H 表示。 数据结构实验报告 实验名称：文件压缩 实验类型：综合性试验 班级：20112111 学号：2011211107 姓名：冯若航 实验日期：2003.6.19 下午4:00 1.问题描述 文件压缩 ①基本要求 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 ●统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件HufTree.dat中。 ●根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并 将字符编码保存到HufCode.txt文件中。 ●压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。 ●解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。 2.数据结构设计 此类问题，应设计文件的数据结构。 * 4 压缩头标记 * 1 文件名长度 * ns 文件名 * 4 源文件长度 * 1020 huffman树 * 1021~EOF 文件内容 赫夫曼树节点的数据结构 typedef struct node { long w; //权 short p,l,r; //父亲，左孩子，右孩子 }HTNODE,*HTNP; //霍夫曼树的结点 赫夫曼编码数组元素的数据结构设计 typedef struct huffman_code { BYTE len; //长度 BYTE *codestr; //字符串 }HFCODE; //霍夫曼编码数组元素 3.算法设计 源代码 #define_CRT_SECURE_NO_DEPRECATE #include 第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7．n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三） （四） （五） （六） （七 ）（八 ） （九 ） （十 ） 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三 ） （四 ） （五 ） （六） （七） （八） （九） （十 ） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设 个空间，问 676(10)，每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ） 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二 分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。 《数据结构》课程设计实验报告 题目：压缩软件（选做题） 姓名： 学号： 指导老师： 时间：2015.09.06 目录 一、设计内容和要求 (3) 二、算法思想描述 (3) 三、程序结构 (4) 四、结果与分析 (5) 结果 (5) 分析 (9) 五、收获与体会 (9) 一、设计内容和要求 设计内容：压缩软件 要求： 建立一个文本文件A（可以是C/C++源程序），统计该文件中各字符频率。首先对各字符进行Huffman编码，将该文件翻译成Huffman编码文件B；然后将Huffman编码文件译码成文件C，并对文件A与C进行比较。 二、算法思想描述 1.Huffman编码解码思想： Huffman树是一种加权路径长度最短的二叉树。编码时，是根据待编码文件中记录的关键字在文件中出现的频率进行编码，每个关键字都对应一个编码，频率较高则编码较短，频率较低则编码较长。Huffman树解码时，根据记录的关键字的编码对文件进行解码。 具体方法为依次选择权值最小的两个关键字作为左右孩子，其和作为父结点的权值，将其父结点代替两个子结点，再次选择权值最小作为左右孩子，依次进行下去，直到所有的关键字结点都成为叶子结点。根据创建的Huffman树来确定个关键字的01编码，左孩子为0，右孩子为1。 2.整体算法描述： 首先读入待压缩文件，然后对每种字符出现的频度进行统计，以频率作为建立哈夫曼树的权值。接着建立哈夫曼树，对出现的每种字符进行哈夫曼编码。此时再读入原文件，逐个字节进行编码，将得到的编码流逐个写入文件。译码过程：读入被压缩文件，根据哈夫曼树对文件中的字符逐个译码，将译码结果逐个写入文件。 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 数据结构试题及答案 一、选择题（每小题2分，共20分），每个题的备选答案中，只有一个是正确的，请将答案填写在试题的括号中。 1、对顺序存储的线性表，设其长度为20，在任何位置上插入或删除操作都是 等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．10 B．9 C．11 D．12 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ B ）语句修改top指针。 A．top++ B．top-- C．top = 0 D．top 4、设入栈顺序为A，B，C，D，E，则出栈序列不可能是（ C ）。A．EDCBA B．ABCDE C．ADEBC D．ABDEC 5、已知关键字序列（46, 79, 56, 38, 40, 84），采用快速排序（以位于最左位 置的关键字为基准）得到的第一次划分结果为：（ A ） A．{ 40, 38, 46, 56, 79, 84 } B．{ 38, 46, 79, 56, 40, 84 } C．{ 38, 46, 56, 79, 40, 84 } D．{ 40, 38, 46, 79, 56, 84 } 6、一个有n个顶点和n条边的无向图一定是（ C ）。 A．不连通的 B．连通的 C．有环的 D．无环的 7、在一棵具有n个结点的二叉树的第i层上，最多具有（ B ）个结点。 A．2i B．2i-1 C．2i+1 D．2n 8、对线性表采用折半查找法，该线性表必须（ B ）。 A．采用顺序存储结构B．采用顺序存储结构，且元素按值有序 C．采用链式存储结构 D．采用链式存储结构，且元素按值有序 9、在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ C ）。A．?(n-1)/2? B．?n/2? C．?n/2? D．?n/2? -1 10、在一个无向图中，所有顶点的度数之和等于所有边数的 ( D ) 倍。 A．3 B．1/2 C．1 D．2 二、填空题（每小题2分，共20分），请将正确的结果，填写在试题的横线上。 1、带头结点的循环链表L为空的条件是。 2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA（以线性数 组表示）。 3、每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________ 排序。 4、设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = = Q.rear，则队列的长度 为。 5、已知数组A[0..11][0..8]按行优先存储，每个元素占有5个存储单元，且 A[0][0]的地址为1000（十进制），则A[6][7]的地址为________________。 6、已知广义表A=(a，()，(b，(c)))，则其深度为。 7、在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6 个，则叶子结点数为__ ____个。 数据结构与程序设计实验实验报告 哈尔滨工程大学 实验报告四 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件HufTree.dat 中。 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并 将字符编码保存到HufCode.txt 文件中。 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件Code。 解压：将Code 文件利用哈夫曼树译码解压，恢复为源文件。 二、数据结构设计 由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。 1.使用结构体数组统计词频，并存储: typedef struct Node{ int weight; //叶子结点的权值 char c; //叶子结点 int num; //叶子结点的二进制码的长度 }LeafNode[N]; 2.使用结构体数组存储哈夫曼树: typedef struct{ unsigned int weight;//权值 unsigned int parent, LChild, RChild; }HTNode,Huffman[M+1]; //huffman树 3.使用字符指针数组存储哈夫曼编码表： typedef char *HuffmanCode[2*M]; //haffman编码表 三、算法设计 1.读取文件，获得字符串 void read_ const *, char *ch){ FILE *in_file = Fopen(, "r"); unsigned int flag = fread(ch, sizeof(char), N, in_file); if(flag == 0){ printf("%s读取失败\n", ); fflush(stdout); } printf("读入的字符串是: %s\n\n", ch); Fclose(in_file); int len = strlen(ch);数据结构试题及答案(免费)
数据结构实验五矩阵的压缩存储与运算学习资料
数据结构试题答案
数据结构整理完整版
数据结构试题及答案
数据结构习题与答案
(完整版)非常实用的数据结构知识点总结
数据结构试题(含答案)
数据压缩
数据结构(5)_文件压缩
数据结构课后习题及解析第六章
十套数据结构试题与答案
数据结构试卷及答案压缩版
压缩软件(数据结构课程设计)
数据结构习题及答案
数据结构试题及答案.docx
数据结构实验报告-文件压缩