搜索
一、选择题（共20分，每题1分）1．从逻辑上可以把数据结构分为两大类,分别是（）。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2.下面给出的四种排序法中()排序法是不稳定的排序法。A.插入B.冒泡C.二路归并D.堆排序3.线性表是具有n个（）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项4.在下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+50;A．O(2n)B．O(n)C．O(n2)D．O(log2n)5.下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示6.栈是一种（）的线性表。A.先进先出B.后进先出C.后进后出D.不分顺序7.设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A.4，3，1，2，B.2，1，3，4，C.1，4，3，2，D.1，2，4，3，8.双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）A.p＾.llink:=q;q＾.rlink:=p;p＾.llink＾.rlink:=q;q^.llink:=p^.llink;B.q＾.llink:=p^.llink;p＾.llink^.rlink:=q;q＾.rlink:=p;p^.llink:=q^.rlink;C.q^.rlink:=p;p^.rlink:=q;p^.llink^.rlink:=q;q^.rlink:=p;D.p^.llink^.rlink:=q;q^.rlink:=p;q^.llink:=p^.llink;p^.llink:=q;9．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表10.树是结点的有限集合，一棵非空的树它有（）根结点。A.有0个或1个B.有0个或多个C.有且只有一个D.有1个或1个以上11．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．求串长D．匹配12．已知串S=‘aaab’,其Next数组值为（）。A．0123B．0012C．1231D．121113.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-114.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定15.深度为h的满m叉树的第k层有（）个结点。(1=k=h)A．mk-1B．mk-1C．mh-1D．mh-116.树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列D.没有对应关系17.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．FEDCBAB．CBEFDAC．CBEDFAD．不确定18.在图的理论与应用中，关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路19.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．420.下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网一、选择题（共20分，每题2分）1.栈是一种（）的线性表。A.先进先出B.后进先出C.后进后出D.不分顺序2.串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。A．2n-1B．n2C．(n2/2)+(n/2)D．(n2/2)+(n/2)-14．从逻辑上可以把数据结构分为两大类,分别是（）。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构5.下面给出的四种排序法中()排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆排序6.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-17.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定8.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。A．选择排序B.冒泡排序C.插入排序D.堆排序9．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。下列排序方法中，哪一个是稳定的排序方法？（）A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序10.树是结点的有限集合，一棵非空的树它有（)根结点。A.有0个或1个B.有0个或多个C.有且只有一个D.有1个或1个以上一、选择题（共20分，每题1分）1．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径2.在一个无向图中，所有顶点的度数之和等于所有边数（）倍。A.1/2B.2C.1D.43.n个顶点的强连通图中至少含有()。A．n-1条有向边B．n条有向边C．n(n-1)/2条有向边D．n(n-1)条有向边4.在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为()A．4B．5C．6D．75.图的逆邻接表存储结构只适用于()图A．有向B．无向C．森林D．连通6.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)/2B.n/2C.nD.(n+1)/27.下面关于二分查找的叙述正确的是()。A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序，而且只能从小到大排列C.表必须有序，且表只能以顺序方式存储D.表必须有序且表中数据必须是整型，实型或字符型8.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A无左孩子的平衡因子为，右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRCRLDRR9．散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是（）。A.2B.3C.4D.510.设要排序（Sort）的数据为：5,1,10,2,15,3，若采用堆排序法（HeapSort）排为升序，则当堆树（Heaptree）第三次建成时，其树根节点数据内容是()。A.3B.10C.15D.511．在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为()。A．O(1)B．O(log2n)C．O(sqt(n))D．O(n)12．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A．60B．66C．18000D．3313.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-114.已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列运算的结果:tail(head(tail(C)))=()。A．（a）B．AC．aD．（A）15.设有一个8阶的对称矩阵A，采用以行优先的方式压缩存储。a11为第1个元素，其存储地址为1，每个元素占一个地址空间。试问元素a85的地址为（）。A．33B．30C．13D．2316.下面说法不正确的是()。A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构17.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④18.对于有n个结点的二叉树,其高度为（）A．nlog2nB．log2nC．|log2n|+1D．不确定19.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-120.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。A．CBEFDAB．FEDCBAC．CBEDFAD．不定一、选择题（共20分，每题1分）1．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。A．O（i）B．O（1）C．O（n）D．O（i-1）2.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）。A.m-nB.m-n-1C.n+1D.条件不足，无法确定3.非空的循环单链表head的尾结点p满足（）。A．p.link==headB．p.link==NILC．p==NILD．p==head4.一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后面向前依次后移（）个元素。A．n-iB．n-i+1C．n-i-1D．i5.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。A．1B．2C．3D．46.在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q-next赋值为（）。A.p-priorB.p-nextC.p-next-nextD.p-prior-prior7.由3个结点可以构造出多少种不同的二叉树？()A．2B．3C．4D．58.关键路径是事件结点网络中（）。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C最长回路D最短回路9．n个结点的完全有向图含有边的数目（）。A.n*nB.n（n＋１）C.n／2D.n*（n－l）10.链栈与顺序栈相比，一个较为明显的优点是()。A.通常不会出现栈空的情形B.插入操作更加便利C.删除操作更加便利D.通常不会出现栈满的情形11．若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是（）。A．iB．n-iC．n-i+1D．不确定12．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A．(rear+1)MODn=frontB．rear=frontC．rear+1=frontD．(rear-l)MODn=front13.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。A．求子串B．联接C．匹配D．求串长14.下面关于串的的叙述中，哪一个是不正确的？（）。A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储15.已知串S=‘aaab',其Next数组值为（）。A．0123B．1123C．1231D．121116.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（）/12。A.35B.37C.39D.4317.数列（21,19,37,5,2）经由冒泡排序法（bubblesort）由小到大排序，在第一次执行交换（swap）的后所得结果为()。A．(19，21，37，5，2)B．(21，19，5，37，2)C．(21，19，