《数据结构c语言》十套数据结构试题及答案

《《数据结构c语言》十套数据结构试题及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构试卷(-)二、填空题(每空1分，共26分)1.通常从四个方面评价算法的质量：、、和。2.一个算法的时间复杂度为(屛+/log2〃+14n)/n2,其数量级表示为。3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树屮所含的结点数为个，树的深度为，树的度为。4.后缀算式923+・102/・的值为o屮缀算式(3+4X)・2Y/3对应的后缀算式为o5.若用链表存储一棵二叉树吋，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有个指针域，其中有个指针域是存放了地址，

2、有个指针是空指针。6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有个和个。7.AOV网是一种的图。8.在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。9.假定一个线性表为(12,23,74,55,63,40),若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的川个子表分别为、、和O10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度11.在堆排序的过程中，对任一分支结点进行筛运算的吋间复杂度为,整个堆排

3、序过程的时间复杂度为012.在快速排序、堆排序、归并排序中，排序是稳定的。三、计算题(每题6分，共24分)1.在如下数组A中链接存储了一个线性表，表头指针为A[0].next,试写出该线性表。605078903440357204101234567Adatanext2.请画出卜图的邻接矩阵和邻接表。SI：S2：p—>next=q；q—>next=NULL；returnL；1请回答下列问题：(1)说明语句SI的功能；(2)说明语句组S2的功能；(3)设链表表示的线性表为(％越，…,如)，写出算法执行后的返回值所表示的线性表。2.vo

4、idABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout«BT->data«'该算法的功能是：五、算法填空(共8分)二叉搜索树的查找一递归算法：boolFind(BTreeNode*BST,ElcmTypc&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){item=BST->data;//查找成功return;}elseif(itcmdata)returnFind(,item);elser

5、eturnFind(,item);)//if}六、编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*IIL,ElemTypex)数据结构试卷(-)二、填空题(24分)1.为了能有效地应用HASH查找技术，必须解决的两个问题是和O2.下面稈序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-l)printf(“o

6、verflow”);else{；；}}3.屮序遍历二叉排序树所得到的序列是序列(填有序或无序)。4.快速排序的最坏时间复杂度为,平均吋I'可复杂度为o5.设某棵二叉树中度数为0的结点数为N。，度数为1的结点数为汕，则该二叉树中度数为2的结点数为；若釆用二叉链表作为该二叉树的存储结构，则该二叉树中共有个空指针域。6.设某无向图屮顶点数和边数分别为n和e,所有顶点的度数之和为d,则e二。7.设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为o8.己知一有向图的邻接表存储结构如下：

7、从顶点1出发，DFS遍历的输出序列是，BFS遍历的输出序列是因的邻接表存储结构三、应用题(36分)1.设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2.设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)o3.设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求计算出查找关键字62时的

8、比较次数并计算出查找成功时的平均查找长度。4.设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。5.设有无向图G,要求给出用普里姆算法