数据结构题目.doc

第一部分填空题：1、数据结构是一门研究非数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算等的学科。 （1） A、操作对象 B、计算方法 C、逻辑存储 D、数据映像 （2） A、结构 B、关系 C、运算 D、算法2、数据结构被形式地定义为（K、R），其中K是（B）的有限集合，R是K上的（D）有限集合。 （1）A、算法 B、数据元素 C、数据操作 D、逻辑结构 （2）A、操作 B、映像 C、存储 D、关系3、线性表的顺序存储结构是一种（A）的存储结构，线性表的链式存储结构是一种（B）存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取4、算法分析的目的是（C），算法分析的两个主要方面是（A） （1）A、找出数据结构的合理性 B、研究算法中的输入和输出的关系 C、分析算法的效率以求改进 D、分析算法的易懂性和文档性 （2）A、空间复杂性和时间复杂性 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性5、计算机算法指的是（C），它必具备输入、输出和（B）等五个特性。 （1）A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、调度方法 （2）A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 C、易读性、稳定性和安全性6、线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）A、正确 B、不正确7、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址（D） A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以8、在以下的叙述中，正确的是（B） A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出9、一个栈的入队序列是a,b,c,d,e，则栈的不可能的输出序列是（C）； A、edcba B、decba C、dceab D、abcde10、若已知一个栈的入栈序列是1，2，3，4，。，n，其输出序列为p1,p2,p3,pn，若p1=n，则pi为（C）。 A、i B、n-i C、n-i+1 D、不确定11、栈结构通常采用的两种存储结构是（A） A、顺序存储结构和链表存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构12、判定一个栈ST（最多元素为m0）为空的条件是（B） A、ST-top0 B、ST-top = 0 C、ST-top m0 D、ST-top=m013、判定一个栈ST（最多元素为m0）为栈满的条件是（D） A、ST-top!=0 B、ST-top = = 0 C、ST-top !=m0 D、ST-top= =m014、栈的特点是（B），队列的特点是（A）。 A、先进先出 B、先进后出15、判定一个队列QU（最多元素为m0）为空的条件是（C）。 A、QU-rear QU-front = = m0B、QU-rear QU-front -1= = m0C、QU-front= = QU-rearD、QU-front= = QU-rear+116、判定一个队列QU（最多元素为m0）为满队列的条件是（A）。 A、QU-rear QU-front = = m0B、QU-rear QU-front -1= = m0C、QU-front= = QU-rearD、QU-front= = QU-rear+117、判定一个循环队列QU（最多元素为m0）为空的条件是（A）。 A、QU-front= = QU-rearB、QU-front! = QU-rearC、QU-front = (QU-rear+1)%m0D、QU-front != (QU-rear+1)%m018、判定一个循环队列QU（最多元素为m0）为满队列的条件是（C）。 A、QU-front= = QU-rearB、QU-front! = QU-rearC、QU-front = = (QU-rear+1)%m0D、QU-front != (QU-rear+1)%m019、循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（A） A、（rear-front+m）%m B、rear-front+1 C、rear-front-1 D、rear-front20、栈和队列的共同点是（C）。 A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点填空4 在线性结构中，第一个结点（0）个前驱结点，其余每个结点有且只有（1）个前驱结点；最后一个结点（0）后续结点，其余每个结点有且只有（1）个后续结点。5 在树形结构中，树根结点没有（父）结点，其余每个结点有且只有（1）个父结点；叶子结点没有（孩子）结点，其余每个结点的孩子结点可以（两个或者一个）。6 在图形结构中，每个节点的前驱节点数和后续结点数可以（任意多个）。7 线性结构中元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中元素之间存在（ 多对多 ）关系。8 算法的五个重要特性是（1）有穷性（2）、确定性（3）、可行性（4）、输入（5）输出。9 下面程序段的时间复杂度是（O(n)）。i=s=0;while (sn)i+;s+=i;18 下面程序段的时间复杂度是（O（n*m）。For (i=0;in;i+) For (j=0;jm;j+) Aij=0;20 下面程序段的时间复杂度是（O（n2）。S=0;For (i=0;in;i+) For (j=0;jn;j+) S+=bij;Sum=s;22 下面程序段的时间复杂度是（O(log3(n)）；i=1；While (itop-l-base=l-stacksize) s-base=(sqstack)realloc(s-stacksize+STACKINCREMENT)*sizeof(int)s-top=s-base+s-stacksize;s-stacksize+= STACKINCREMENT;*(l-top)=e; l-top+;24 对栈进行退栈时的操作是int POP(sqstack *l) int e; If(l-top=l-base) return ERROR; *(l-top)=e; l-top-; return e;25 在一个循环队列中删除一个元素时，其操作是（）26 在具有n个单元的循环队列中，队满时共有（n-1）个元素。27 一个栈的输入序列是12345，则栈的输出序列43512是（）。28 一个栈的输入序列是12345，则栈的输出序列12345是（）。分析题：5 对于一个栈，给出输入项A、。如果输入项序列由，所组成，试给出全部可能的输出序列。（、分别仅入栈一次。）6 有字符串次序为，试利用栈排出将次序改变为的操作步骤。第二部分选择题2 不带头结点的单链表head为空的判定条件是（B）；A、head=NULL B、head-next=NULLC、head-next=head D、head!=NULL3 带头结点的单链表head为空的判定条件是（A）；A、head=NULL B、head-next=NULLC、head-next=head D、head!=NULL3、非空的循环单链表head的尾结点（由p所指向）满足（C）。 A、p-next=NULL B、p=NULL C、p-next=head D、p=head4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（C）。 A、s-next=p-next; p-next=s; B、p-next=s-next; s-next=p;C、q-next=s; s-next=p; D、p-next=s; s-next=q;5、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。 A、s-next=p; p-next=s; B、s-next=p-next; p-next=s; C、s-next=p-next; p=s; D、p-next=s; s-next=p;6、在一个单链表中，若删除p所指结点的后续结点，则执行（A）。 A、p-next=p-next-next; B、p=p-next;p-next=p-next-next; C、p-next=p-next; D、p=p-next-next;7、从一个具有n结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（D）个结点。 A、n B、n/2 C、(n-1)/2 D、(n+1)/28、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）。 A、O(1) B、O(n) C、O(n2) D、O(nlog2n)9、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（B）。 A、HS-next=s; B、s-next=HS-next; HS-next=s; C、s-next=HS; HS=s; D、s-next=HS; HS=HS-next;10、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除结点的值，则执行（D）。 A、x=HS; HS=HS-next; B、x=HS-data;C、HS=HS-next; x=HS-data; D、x=HS-data; HS=HS-next;11、在一个链队中，假设f和r分别为队尾和队首指针，则插入s所指结点的运算时（B）。 A、f-next=s; f=s; B、r-next=s; r=s; C、s-next=r; r=s; D、s-next=f; f=s;12、在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时（C）。 A、r=f-next; B、r=r-next; C、f=f-next; D、f=r-next;填空题1 单链表是（线性表）的链接存储表示。2 可以使用（双链表）表示树型结构。3 在双链表中，每个结点有两个指针域，一个指向（前驱结点），另一个指向（后继结点）。4 在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：a、s-next=（ p-next ）；b、p-next=s;c、t=p-data;d、p-data=( s-data );e、s-data=( t );14 带有一个头结点的单链表head为空的条件是（head=NULL）。15 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next=(1)和p-next=（2）的操作。16 非空的循环单链表head的尾结点（由p所指向），满足条件（1）。17 在栈顶指针为HS的链栈中，判定栈空的条件是（1）。18 在栈顶指针为HS的链栈中，计算该链栈中结点个数的函数是（1）。19 在HQ的链队中，判定只有一个结点的条件是（1）。20 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（1）；在给定值为x的结点后插入一个新结点的时间复杂度是（2）。21分析设计题10 假设Q1，10是一个顺序队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队20 假设Q1，10是一个循环队列，初始状态为front=rear=1，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队树选择题3 如下图所示的4棵二叉树中，（C）不是完全二叉树。A、 B、C、 D、6 在线索化二叉树中，t所指结点没有左子树的充要条件是（B）。A、t-left=NULL; B、t-ltag=1;C、t-ltag=1且t-left=NULL D、以上都不对。10 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法（B）。A、正确 B、错误13 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法（A）。A、正确 B、错误15 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。A、2h B、2h-1 C、2h+1 D、h+116 如下图所示二叉树的中序遍历序列是（B）。A、abcdgef B、dfebagc C、dbaefcg D、defbagc18 下图二叉树所示，其中序遍历的序列为（dgbaechf）。19 深度为5的二叉树至多有（C）个结点。A、16 B、32 C、31 D、1021 在一非空二叉树的中序遍历序列中，根结点的右边（A）。A、只有右子树上的所有结点 B、只有右子树上的部分结点C、只有左子树上的部分结点 D、只有左子树上的所有结点22 树最适合用来表示（C）。A、有序数据元素 B、无序数据元素C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据23 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（C）。A、不发生改变 B、发生改变 C、不能确定 D、以上都不对28 对一个满二叉树，m个树叶，n个结点，深度为h，则（D）。A、n=h+m B、h+m=2n C、m=h-1 D、n=2h-131 设n, m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（C）。A、n在m右边 B、n是m祖先 C、n在m左边 D、n是m子孙32 线索二叉树是一种（B）结构。A、逻辑 B、逻辑和存储 C、物理 D、线性 33具有五层结点的二叉平衡树至少有（B）个结点。 A、10 B、12 C、15 D、17填空题2 如下图一棵树，回答下面的问题：a、这棵树的根结点是（K1）。b、这棵树的叶子结点是（K2,K5,K7,K4）。c、结点k3的度是（2）。d、这棵树的度是（3）。e、这棵树的深度是（4）。6 指出树和二叉树的三个主要差别7 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如下图所示，则该二叉树的链接表示形式为（）。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21eafdgcjlhib16 深度为k的完全二叉树至少有（2(k-2)-1）个结点，至多有（2(k-1）个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（2k）。17 在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=（n2+1）。18 一棵二叉树的第i（i=1）层最多有（2(i-1)）个结点；一棵有n个结点的满二叉树共有（2(n-1)）个叶子和（2(n-1)-1）个非终端结点。分析题1、 现有按中序遍历二叉树的结构为abc，问有几种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是什么？2、 如下图所述的二叉树，回答以下问题： a、 给出其前序遍历、后序遍历、中序遍历的序列结果。先序：abdgcefhi 后序：gdbeihfca 中序：dgbaechifb、 给出该二叉树的中序线索二叉树、后序线索二叉树。中序：3、 已知一棵树如下图所示，用孩子兄弟表示法表示。4. 以4，5，6，7，10，12，18为结点权值，给出构造Huffman树的过程。 5. 设二叉树Bt的存储结构如下图： 其中left、right分别为结点的左右孩子指针域，data为结点的数据域，根结点为序号6的结点，请完成下列各题。（1）、画出二叉树Bt的逻辑结构；（2）、写出按先序、中序和后序遍历二叉树Bt所得到的结点序列；（3）、画出二叉树Bt的后线索化树。6、二叉树结点数组采用顺序存储结构，如下图所示： （1）、画出二叉树表示；e a f d g c j h i b （2）、写出先序、中序遍历和后序遍历的结果；先序：eadcbjfghi 中序：abcdjefhgi 后序：bcjdahigfe （3）给出结点c的父结点，及其左右孩子结点。父节点：d；左孩子：b；右孩子：NULL;6. 设数据集合d=1，12，5，8，3，10，7，13，9，试完成下列各题：（1） 依次取d中各数据，构造一棵二叉排序树Bt；（2） 如何依据此二叉树Bt得到d的一个