数据结构试题一
一、单项选择题（每小题3分，共30分）
1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。
A、不确定 B、2n      C、2n+1      D、2n-1
2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是字符串）。
A、[da，ax，eb，de，bb]ff[ha，gc]                  B、[cd，eb，ax，da]ff[ha，gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha]                  D、[ax，bb，cd，da]ff[eb，gc，ha]
3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。
A、单链表    B、双链表    C、单循环链表      D、顺序表
4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。
A、堆排序    B、冒泡排序  C、直接选择排序    D、快序排序
5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉树。
          A、空或只有一个结点                  B、高度等于其结点数
C、任意结点无左孩子                  D、任意结点无右孩子
6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的 是（ ）。
      A、堆排序      B、冒泡排序      C、直接选择排序    D、快序排序
7、快速排序算法在最好情况下的时间复杂度为（ ）。
A、O(n)        B、O(n 2 )        C、O(nlogn)        D、O(logn)
8、已知数据表 A中每个元素距其最终位置不远，则采用（ ）排序算法最 省时间。
A、堆排序      B、插入排序      C、直接选择排序    D、快序排序
9、带权有向图G用邻接矩阵 A存储，则顶点 i的入度为 A中（ ）。
A、第 i行非∞的元素之和          B、第 i列非∞的元素之和
C、第 i行非∞且非 0的元素之和    D、第 i列非∞且非 0的元素之和
10、在有 n个结点且为完全二叉树的二叉排序树中查一个键值，其平均比 较次数的数量级为（ ）。
A、O(n)      B、O(n 2 )      C、O(nlogn)        D、O(logn)
二、判断题 （认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，共10分）
1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问该图的每个顶点。                                (  )
2. 在索引顺序表上实现分快查，在等概率查情况下，其平均查长度不仅与表的个数有关，而且与每一块中的元素个数有关。        (  )
3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。  (  )
4、图G的最小生成树的代价一定小于其他生成树的代价。        (  )
5、已知一棵树的先序序列和后序序列，一定能构造出该树。      (  )
6、对一个堆按层次遍历，不一定能得到一个有序序列。          (  )
7、设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT 中的结点也一定是叶子结点。                              (  )                                           
8、不管 ADT栈是用数组实现，还是用链表的指针实现，POP(S)与Push(x,S) 的耗时均为 O(n)。                                          (  )           
9、如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入 上去，一定能得到原来的二叉排序树。                            (  )先序中序后序遍历二叉树
10、快速排序是排序算法中最快的一种。                        (  )
三、填空题（每小题2分，共20分）
1、在双向循环表中，在 p所指的结点之后插入指针 f所指的结点，其操作为 ：
___ ______=p;f→next=p→next;_____=f; p→next=f。
2、在有序表 A[1…20]中，采用二分查算法查元素值等于 A[12]的元素，所比较过的元素的下标依次为__________。
3、若某串的长度小于一个常数，则采用_________存储方式最节省空间。
4、在有 n个顶点的有向图中，每个顶点的度最大可达_________。
5、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 __________。
6、设键值序列为{K1，K2，…，Kn},用筛选法建堆则必须从第_______个元 素开始筛选。
7、在二叉链表中判断某指针p所指结点为叶子结点的条件是_________。
8、直接选择排序算法在最好情况下所作的交换元素的次数为___ _____。
9、有n个球队参加的足球联赛按主客场制进行比赛，共需进行_______比赛。
10、下列排序算法中， 占用辅助空间最多的是_________( 堆排序， 希尔排序， 快速排序，归并排序)。
四、简答题（每题10分，共60分）
1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？
2、设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表中，请回答以下问题：
（1）设计一个适合该散列表的散列函数。
（2）用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为多少？
3、对 n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问
（1）图中有多少条边？
（2）任意两个顶点 i和 j是否有边相连？
（3）任意一个顶点的度是多少？
4、已知下面二叉排序树的各结点的值依次为1…9，请标出各结点的值。
5、具有3个结点的树和具有3个结点的二叉树,它们的所有不同形态有哪些？
6、分析以下程序段中语句x=x+y的执行次数。
                x=0; y=0;
                for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=1;k<=j;k++)
x=x+y;
五、算法设计题（每题15分，共30分）
说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。
1、假设以二叉链表作为二叉树存储结构，其类型定义如下：
typedef struct node
{  char data;
struct node *lchild,*rchild;//左右孩子指针
}BinTNode,*BinTree;
写一函数，完成以下功能：
对二叉树中每个结点，如果其左孩子为空（右孩子不为空），则将其右孩子设置为左孩子。
2、试设计将数组 A[0…n-1]中所有奇数移到所有偶数之前的算法。要求不另增加存储空间且时间复杂度为O(n)。
数据结构试题1参考答案
一、1——5：DADAB        6——10：CCBDD
二、1——5：ⅹ√ⅹⅹ√    6——10：√ⅹⅹⅹⅹ
三、 1、①f→prior， ②p→next→prior  2、10  15  12    3、顺序压缩  4、2(n-1)        5、129    6、n/2的最小整数  7、(p→lchild==NULL)&&(p→rchild==NULL)
8、0          9、n(n-1)      10、归并排序
四、1、 答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。双链表 的删除时间复杂度为O(1)，单循环链表删除p 结点的时间复杂度为O(n)。
2、答案：（1）由于散列表的长度为12，则可选不超过表长的最大素数11作为除留余 数法的模，则可得其散列函数为h(k)=k%11。
（2）若用线性探测法解决冲突，则可构造出散列表如下：
13
14
35
17
29
153
0        1      2    3      4      5      6      7      8      9    10
11
此时，其装填因子为6/12=1/2，若用链式法解决冲突，则其散列表为：
     
3、 答案：（1）无向图的邻接矩阵所有数值之和除以2，为边数。有向图邻接矩阵各行 数值之和为总边数。邻接表表示无向图内部顶点个数除以 2，有向图内部顶 点个数。
（2）无向图中 I 行和 J 列的交叉点的值是否为 1。有向图 I 行 J 列交叉点或 I列和 J行交叉点的值为1。
（3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数 值之和。
4答案：
5、答案：具有3个结点的树的形态为：三个结点的两种树形态，无左右之分。
具有3个结点的二叉树的形态为：5种形态，有左右之分。
6：答案：
五、1、 答案：    void exchange(Bin Tree T)
{ if(T)
{ if(!T→lchild&&T→rchild)
{T→lchild= T→rchild;
T→rchild=NULL; }
exchange(T→lchild);
exchange(T→rchild); }}
2、 答案： int oddbefore(A,n)//将数组 A[0…n-1]中所有奇数移到所有偶数之前
int A[ ];
{ int c,i,j; i=0;j=n-1;//初始化 i、j

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。