1、C语言数据结构复习题一、单选题1. 在数据结构中，从逻辑上可以把数据结构分为（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构2. 算法具备输入，输出和（ ）等五个特性A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性3. 链表不具备的特点是（ ）。A可随机访问任一结点B插入删除不需要移动元素C不必事先估计存储空间D所需空间与其长度成正比4线性表是（ ）。 A一个有限序列，可以为空 B一个有限序列，不可以为空C一个无限序列，可以为空 D一个无限序列，不可以为空5下面关于线性表的叙述中，错误
2、的是哪一个? （ ）。A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链式存储，不必占用一片连续的存储单元D线性表采用链式存储，便于进行插入和删除操作。6以下关于线性表的说法不正确的是（）。A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。7设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（）。 AA, B, C, D, E BB, C, D, E, AC
3、E, A, B, C, D DE, D, C, B, A8在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）。 Atop不变 Btop=0 Ctop- Dtop+9在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是（）。Afrontrear1 Brearfront1 Cfrontrear Dfront010若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“BeijingNanjing”，T=“jing”，INDEX（S，T）=（）。A.2 B.3 C.4 D.511串
4、是一种特殊的线性表，其特殊性体现在（）。A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符12稀疏矩阵一般的压缩存储方法有两种，即（）。A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表 D.散列和十字链表13对矩阵进行压缩存储是为了（）。A方便运算B方便存储C提高运算速度 D减少存储空间14假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A. 15 B. 16 C. 17 D. 4715树最适合用来表示（ ）。A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据16根据先序序列ABDC（根左右）
5、和中序序列DBAC（左根右）确定对应的二叉树，该二叉树（ ）。A. 是完全二叉树 AB. 不是完全二叉树 B CC. 是满二叉树 D D. 不是满二叉树 17已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为( )。A. 1 B. 2 C. 3 D. 4 12 34 5 6 78 918对于一个无向图，下面( )种说法是正确的。A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和C. 每个顶点的入度为0 D. 每个顶点的出度为019对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( )。A. 3 B. 4 C. 5 D. 620若要对100
6、0个元素排序，要求既快又节省存储空间，则最好采用（ ）方法。A. 直接插入排序 B. 归并排序 C. 堆排序 D. 快速排序二、判断题1. 顺序存储方式只能用于存储线性结构。（ F ）2. 已知指针P指向键表L中的某结点，执行语句P=P.next不会删除该链表中的结点。（ T ）3. 队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（ F ）4.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ F ）5. 用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（ T ）6.快速排序是不稳定排序。
7、（ T ）7. 在哈夫曼树中，权值最小的结点离根结点最近。（ F ）8.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（ T ）9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（ F ）10.冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（ F ）三、填空题1数据的逻辑结构有四种基本形态，分别是集合、( 线性表 )、树和图。2. 一个算法的效率可分为时间效率和( 空间 )效率。3在单链表中，要删除某一指定的结点，必须找到该结点的（ 前驱 ）结点。4当对一个线性表经常进行插入和删除操作时，采用( 链式 )存储结构为宜。5
8、对于队列而言，只能在（ 队尾 ）位置插入元素。7稀疏矩阵一般的压缩存储方法有两种，即（ 三元组 ）和十字链表。8 在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0（ n2+1 ）。9. 三叉链表比二叉链表多一个指向（ 双亲 ）的指针域。10. 具有10个顶点的无向图，边的总数最多为（ 45）。N(N-1)/2四、综合应用题要点1.二叉树先序遍历、中序遍历、后序遍历 根左右 左根右 左右根要点2.哈夫曼树的生成 排序 选数 连接最小的数 比较 要点3.森林和二叉树的相互转换 要点4.将图转换成最小生成树要点5.根据稀疏矩阵对应的三元组线性表，画出稀疏矩阵要点6.根据
9、无向图或者有向图的邻接表，画出无向图或者有向图要点7.求最短路径的Dijkstra算法五、算法设计题。要点：着重关注单链表的基本操作（数据插入、删除、判断单链表是否为空，返回单链表元素个数等），栈或者队列两种结构链式或者顺序存储结构定义中的方法。比如出栈（队列）、进栈（队列），获取栈（队列）首元素，判断栈（队列）是否为空等等。#include#define MAXSIZE 20 #define OK 1#define ERROR 0typedef int Status; typedef int ElemType;typedef struct ElemType dataMAXSIZE; int
10、length; / 线性表中元素个数SqList;/初始化线性表SqList InitList() SqList L; L.length=0; return L;/插入元素Status ListInsert(SqList *L,int i,ElemType e) int k; if(L-length=MAXSIZE | iL-length) return ERROR; for(k=L-length-1;k=i;k-) L-datak+1=L-datak; L-datai=e; L-length+; return OK;/获取元素ElemType GetElem(SqList L,int i)
11、if(L.length=0 | iL.length-1) printf(位置错误！); return L.datai;/删除元素Status ListDelete(SqList *L,int i,ElemType *e) int k; if(L-length=0 | iL-length-1) return ERROR; *e=L-datai; for(k=i;klength;k+) L-datak-1=L-datak; L-length-; return OK;/清空线性表void ClearList(SqList *L) L-length=0;/判断线性表是否为满Status ListFul
12、l(SqList L) if(L.length=MAXSIZE) return OK; else return ERROR; /判断线性表是否为空Status ListFull(SqList L) if(L.length=0) return OK; else return ERROR; int main() Status x; ElemType y,*e,z; SqList L=InitList(); ListInsert(&L,0,20); ListInsert(&L,1,40); ListInsert(&L,2,80); /y=GetElem(L,1); e=&y; ListDelete(&L,1,e); z=GetElem(L,1); printf(%dn,z); /ClearList(&L); return 1;
