C语言数据结构复习题

-z.一、单项选择题1.在数据构造中，从逻辑上可以把数据构造分为〔〕。A．动态构造和静态构造B．紧凑构造和非紧凑构造C．线性构造和非线性构造D．部构造和外部构造2.算法具备输入，输出和〔〕等五个特性A.可行性，可移植性和可扩大性B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和平安性3.链表不具备的特点是〔〕。A．可随机访问任一结点B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与其长度成正比4．线性表是〔〕。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空5．下面关于线性表的表达中，错误的选项是哪一个?〔〕。A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进展插入和删除操作。C线性表采用链式存储，不必占用一片连续的存储单元D线性表采用链式存储，便于进展插入和删除操作。6．以下关于线性表的说法不正确的选项是〔〕。A．线性表中的数据元素可以是数字、字符、记录等不同类型。B．线性表中包含的数据元素个数不是任意的。C．线性表中的每个结点都有且只有一个直接前趋和直接后继。D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。7．设有一个栈，元素的进栈次序为A,B,C,D,E,以下是不可能的出栈序列〔〕。A．A,B,C,D,E B．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A8．在一个具有n个单元的顺序栈中，假定以地址低端〔即0单元〕作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为〔〕。A．top不变 B．top=0 C．top-- D．top++9．在循环队列中，假设front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是〔〕。A．front＝＝rear＋1B．rear＝＝front＋1C．front＝＝rearD．front＝＝010．假设INDE*〔S，T〕表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing〞，T=“jing〞，INDE*〔S，T〕=〔〕。A.2B.3C.4D.511．串是一种特殊的线性表，其特殊性表达在〔〕。A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符12．稀疏矩阵一般的压缩存储方法有两种，即〔〕。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表13．对矩阵进展压缩存储是为了〔〕。A．方便运算B．方便存储C．提高运算速度D．减少存储空间14．假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为〔〕个。A.15B.16 C.17 D.4715．树最适合用来表示〔〕。A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据16．根据先序序列ABDC〔根左右〕和中序序列DBAC〔左根右〕确定对应的二叉树，该二叉树〔〕。A.是完全二叉树 AB.不是完全二叉树BCC.是满二叉树DD.不是满二叉树17．一棵完全二叉树的结点总数为9个，则最后一层的结点数为()。A.1 B.2C.3D.41

234567

8918．对于一个无向图，下面()种说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度之和C.每个顶点的入度为0 D.每个顶点的出度为019．对于长度为18的顺序存储的有序表，假设采用折半查找，则查找第15个元素的比拟次数为()。A.3B.4C.5D.620．假设要对1000个元素排序，要求既快又节省存储空间，则最好采用〔〕方法。A.直接插入排序B.归并排序C.堆排序D.快速排序二、判断题1.顺序存储方式只能用于存储线性构造。〔F〕2.指针P指向键表L中的*结点，执行语句P=P.ne*t不会删除该链表中的结点。〔T〕3.队列是一种插入和删除操作分别在表的两端进展的线性表，是一种先进后出的构造。〔F〕4.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。〔F〕5.用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。〔T〕6.快速排序是不稳定排序。〔T〕7.在哈夫曼树中，权值最小的结点离根结点最近。〔F〕8.假设图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条〔其中n为G的顶点数〕。〔T〕9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。〔F〕10.冒泡排序算法关键字比拟的次数与记录的初始排列次序无关。〔F〕三、填空题1．数据的逻辑构造有四种根本形态，分别是集合、(线性表)、树和图。2.一个算法的效率可分为时间效率和(空间)效率。3．在单链表中，要删除*一指定的结点，必须找到该结点的〔前驱〕结点。4．当对一个线性表经常进展插入和删除操作时，采用(链式)存储构造为宜。5．对于队列而言，只能在〔队尾〕位置插入元素。7．稀疏矩阵一般的压缩存储方法有两种，即〔三元组〕和十字链表。8．在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0＝〔n2+1〕。9.三叉链表比二叉链表多一个指向〔双亲〕的指针域。10.具有10个顶点的无向图，边的总数最多为〔45〕。N(N-1)/2四、综合应用题要点1.二叉树先序遍历、中序遍历、后序遍历根左右左根右左右根要点2.哈夫曼树的生成排序选数连接最小的数比拟要点3.森林和二叉树的相互转换要点4.将图转换成最小生成树要点5.根据稀疏矩阵对应的三元组线性表，画出稀疏矩阵要点6.根据无向图或者有向图的邻接表，画出无向图或者有向图要点7.求最短路径的Dijkstra算法五、算法设计题。要点：着重关注单链表的根本操作〔数据插入、删除、判断单链表是否为空，返回单链表元素个数等〕，栈或者队列两种构造链式或者顺序存储构造定义中的方法。比方出栈〔队列〕、进栈〔队列〕，获取栈〔队列〕首元素，判断栈〔队列〕是否为空等等。#include<stdio.h>#defineMA*SIZE20#defineOK1#defineERROR0typedefintStatus;typedefintElemType;typedefstruct {ElemTypedata[MA*SIZE]; intlength;//线性表中元素个数}SqList;//初始化线性表SqListInitList(){ SqListL; L.length=0; returnL;}//插入元素StatusListInsert(SqList*L,inti,ElemTypee){ intk; if(L->length==MA*SIZE||i<0||i>L->length) { returnERROR; } for(k=L->length-1;k>=i;k--) { L->data[k+1]=L->data[k]; } L->data[i]=e; L->length++; returnOK;}//获取元素ElemTypeGetElem(SqListL,inti){ if(L.length==0||i<0||i>L.length-1) { printf("位置错误！"); } returnL.data[i];}//删除元素StatusListDelete(SqList*L,inti,ElemType*e){ intk; if(L->length==0||i<0||i>L->length-1) { returnERROR; } *e=L->data[i]; for(k=i;k<L->length;k++) { L->data[k-1]=L->data[k]; } L->length--; returnOK;}//清空线性表voidClearList(SqList*L){ L->length==0;}//判断线性表是否为满StatusListFull(SqListL){ if(L.length==MA*SIZE) { returnOK; } else { returnERROR; }}//判断线性表是否为空StatusListFull(SqListL){ if(L.length==0) { returnOK; } else { returnERROR; }}intmain(){ Status*; ElemType