数据结构(c语言)试卷（5）

《数据结构(c语言)试卷（5）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、成都东软信息技术学院200~200学年第学期期末试题——数据结构（C语言）题号一二三四五总分分数说明：本试卷共五大题，试卷满分100分，考试时间120分钟。一．单项选择题：共10小题、每题2分，满分20分；将答案填入题中的括号中。1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素。A、n-iB、n-i+1C、n-i-1D、i2．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行。A、HL=p;p->next=HL;B、

2、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;3．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行。A、p=q->next;p->next=q->next;B、p=q->next;q->next=p;C、p=q->next;q->next=p->next;D、q->next=q->next->next;q->next=q;4．栈的插入与删除操作在进行。A、栈顶B、栈底C、任意位置D、指定位置5．若让元

3、素1，2，3依次进栈，则出栈次序不可能出现种情况。A、3，2，1B、2，1，3C、3，1，2D、1，3，26．在一个循环顺序队列中，队首指针指向队首元素的位置。A、前一个B、后一个C、当前D、后面7．在所有排序方法中，关键字比较次数与记录的初始排列次序无关的是。A、直接插入排序B、起泡排序C、快速排序D、直接选择排序8．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是。A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL9

4、.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。A、24B、48C、72D、5310.组成数据的基本单位是。A、数据项B、数据类型C、数据元素D、数据变量二．判断题：共10小题，每小题1分，满分10分；请将答案以“√”、“×”7形式填入题后括号中。1．无向图的邻接矩阵一定是对称矩阵。（）2．任意一棵满二叉树一定也是完全二叉树。（）3．如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。（）4．有向图邻接矩阵的第i行

5、的所有元素之和等于第i列的所有元素之和。（）5．进栈操作时，必须判断栈是否已满。（）6．线性表的唯一存储形式就是链表。（）7．一个强连通图的连通分量只有一个。（）8．数据元素是数据的最小单元。（）9．满二叉树的叶子结点一定都在最后一层。（）10．完全二叉树的叶子结点可能都在最后一层。（）三．填空题：共10小题，每题3分，满分30分；请将一个正确答案的序号填入括号中。1.数据的逻辑结构被分为__________、_________、__________和__________四种。2.在线性结构、树形

6、结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。3.设一棵二叉树有50个叶子结点，则共有个度为2的结点。4．在一个图中，所有顶点的度数之和等于所有边数的________倍。5．在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。6．表示图的三种存储结构为________、________和________。7．在对一组记录（54，38，96，23，15，72，60，45

7、，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较次。8．在线性表的________存储中，对每一个元素只能采用顺序查找。9．对n个元素的序列进行起泡排序时，最少的比较次数是。10.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为________________。四．应用题：共3小题，每题10分，满分30分。1.已知一棵二叉树的中序遍历结果为DBHEAFICG，前序遍历结果为ABDEHCFIG，画出该二叉树。2.已知一棵完全二叉树的顺序存储结构如下表

8、所示，试画出该完全二叉树的逻辑示意图。3.已知有二叉树如右图所示。（1）写出各结点的度。7（2）画出右图二叉树对应的二叉链表存储结构示意图。ABCDIEFHG五．算法描述题：共1小题，每题10分，满分10分；用任何程序语言、伪语言或流程图描述下列算法。1．设计一个算法，将一顺序栈中的元素依次取出，并打印元素值。已知顺序栈的数据结构如下：Typedefstruct{intdata[100]；inttop；}SeqStack；7答案及评分标准：数据结构（C语言）答案及评分标准一．单项选