桂电2018数据结构试题及答案

一、 单项选择（每题2分，共50分）1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间（B）和运算的学科。A、结构 B、关系 C、运算 D、算法2、计算机算法指的是（B）。   A、程序                 B、问题求解步骤的描述  C、调度方法               D、排序方法3、数据结构有（D）种基本逻辑结构。 A、1 B、2 C、3 D、44、线性表采用链式存储时,其地址(D)。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续与否均可以5、已知L是带表头附加结点的单链表，删除第一个结点的语句是(B)。$ d2 G" - e4 5 _5 ( D: v/ ?    A、LL->link；    B、L->1ink=L->link->link；免费电大作业答案  C、 LL；    D、  L->1ink=L；卓越人6、设入栈序列的顺序为：A、B、C、D，在入栈操作的同时，,随时可能有出栈操作，不能实现的输出序列列为（C）。 A、CDBA B、 BDCA C、ADBC D、CBAD7、队列是限定在（C）处进行插入操作的线性表。A、端尾 B、队头C、队尾 D、中间8、深度为4(根的层次为1)的二叉树至多有（A）结点。A、 15              B、 14             C、13                D)、129、假设一棵三叉树的结点数为50，则它的最小高度为（C）。 A、3 B、4 C、5 D、6 10、结点总数为n的完全二叉树中，其非叶结点数为(A)。其中，运算符“/”为整除符。A、n/2 B、(n-1)/2 C、(n+1)/2 D、( n-2)/211、下面叙述正确的是（A）。A、二叉树是特殊的树 B、二叉树等价于度为2的树C、完全二叉树必为满二叉树 D、二叉树的左右子树有次序之分12、假设在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点数为（B）个。 A、15 B、16 C、17 D、4713、哈弗曼树是一类带权路径长度（A）的树。 A、最小 B、最大 C、不确定 D、以上都不对14、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为（A）。As Bs-1 Cs+1 Dn15、在一个具有n个顶点的有向完全图中，所含的边数为（B）。An Bn(n-1) Cn(n-1)/2 Dn(n+1)/2 16、由一个具有n个顶点的连通图生成的最小生成树中，具有（B）条边。An Bn-1 Cn+1 D2n17、设有向图G的二元组定义如下：其中，V=vl，v2，v3，v4 E=<v1，v4>，<v3，v1>，<v3，v4>，<v4，v3>则叙述中，正确的是(C)。 A、顶点v1的入度为2 B、顶点v2的出度为1 ， C、顶点v3和顶点v4间的弧数为2 D、G的强连通分量数为118、从未排序序列中挑选元素，将其放入已排序队列的一端，此方法为（C）A、选择排序 B、冒泡排序 C、插入排序 D、归并排序19、假定对元素序列（7,3,5,9,1,12,8,15）进行快速排序，则进行第一次划分后，得到左区间中元素的个数为（B）。A、2 B、3 C、4 D、520、二分查找要求被查找的表是（C）。A、键值有序的链接表                    B、链接表但键值不一定有序C、键值有序的顺序表                    D、顺序表但键值不一定有序二、 程序填空（每空2分，共10分）1、下列函数的功能是：在指定数组中查询与变量x相同的值，若数组中某个元素的值等于x的值，则返回该元素的下标，如果查不到返回-1。填空完成程序。 int seq_search (int array ,int n,int x) /在数组中查找关键字值int i；for (i=0; i<n ;i+) /从数组中的第一个元素开始向后扫描if(_arrayi=x_) return i；;else return_-1_；2、 直接选择排序的基本思想是：第一次从所有记录中选取最小关键字的记录，与第一个记录交换，然后在其余的记录中（第一个除外）再选出次小关键字的记录与第二个记录交换位置，依次类推，直到所有记录均排好序为止。试完成下列直接选择排序算法。Void Selectsort(int array,int n)int i，j，k； int x； for(i0；i<n-2；i+) ki； for(ji+1；j<=n-1；j+) /选择最小关键字 if (_arrayj<arrayk_) k=j; /记录最小关键字记录的位置 if (k!=i)/交换最小关键字记录的位置 x=arrayi；_arrayi=arrayk_；_arrayk=x_；简单题（每题10分，共50分）1、 分别写出题图1中二叉树的前序、中序、后序遍历序列。前序：ABCDEFGH中序：BCAEDGFH后序：CBEGHFDA图1 2、已知无向图G的邻接矩阵如图2所示。请画出该无向图，并写出按深度优先搜索和广度优先搜索时时的访问序列。43210 深度优先搜索：v0v1v3v4v2广度优先搜索：v0v1v2v3v4图23、设待排序记录的关键字为68，21，33，11，26，87，45，22，试对其进行冒泡排序，写出整个冒泡排序的每一趟过程。21，33，11，26，68，45，22，8721，11，26，33，45，22，68，8711，21，26，33，22，45，68，8711，21，26，22，33，45，68，8711，21，22，26，33，45，68，874、已知Hash函数为 H（K）=K mod 13 ，散列地址为0-12，用线性探测处理冲突，给出关键字（32，75，63，48，94，25，36，18，70）在散列地址的分布。01234567891011123694183270487563255、.题5图中二叉排序树的各结点的值分别为19，请在图中标出各结点的值。852764193题5图