数据结构难题汇集.doc

14 . 设单链表中结点的结构为（data,link），单链表中指针p所指结点不是尾结点，若在*p之后插入结点*s，应执行（）操作。A. s-Link=p; p-Link=s； B. s-Link=p-Link; p-Link=s； C. s-Link=p-Link; p =s；D. p-Link=s； s-Link=p；输入答案： B答题正确 16 . 以下关于线性表的说法不正确的是_。A. 线性表中的数据元素可以是数字、字符、记录等不同类型。 B. 线性表中包含的数据元素个数不是任意的。 C. 线性表中的每个结点都有且只有一个直接前趋和直接后继。D. 存在这样的线性表：表中各结点都没有直接前趋和直接后继。输入答案： C答题正确 22 . 设链式栈中结点的结构为(data,link)且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除的值保存到x中，则应执行（ ）操作。A. xtop-data; top=top-link； B. top=top-link; x=top-data; C. x=top; top=top-link;D. x=top-data;输入答案： A答题正确 27 . 一个广义表的表头总是一个（ ）。A. 广义表 B. 元素 C. 空表 D. 元素或广义表正确答案： D 32 . 如果F是由有序树T转换而来的二叉树，那么T中结点的后序就是F中结点的（ ）。A. 中序 B. 前序 C. 后序 D. 层次序正确答案： A 34 . 下面叙述正确的是（ ）。A. 二叉树的第i层最多有2i-1个结点 B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树D. 二叉树的左右子树有次序之分输入答案： D答题正确 36 . 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（ ）。A. 1 B. 2 C. 3D. 4输入答案： B答题正确 37 . 对包含n个元素的散列表进行搜索，搜索成功时的平均搜索长度（ ）A. 为O（log2n）。 B. 为O（n）。 C. 不直接依赖于n。D. 上述三者都不是。正确答案： C 38 . 若查找每个元素的概率相等，则在长度为n的顺序表上顺序查找任一元素的平均查找长度为()。A. n B. n+1 C. (n-1)/2D. (n+1)/2输入答案： D答题正确 39 . 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为()。A. 3 B. 4 C. 5D. 6输入答案： B答题正确 40 . 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为()。A. 2 B. 3 C. 4D. 5正确答案： C 答题错误 41 . 对具有n个元素的有序表采用折半查找，则算法的时间复杂度为( )。A. O(n) B. O(n2) C. O(1)D. O(log2n)输入答案： D答题正确 42 . 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度的时间复杂度为（ ）。A. O(n) B. O(1) C. O(log2n) D. O(n*n)输入答案： A答题正确 43 . 假定对长度n=50的有序表进行折半查找，则对应的树高度为（ ）。A. 5 B. 6 C. 7D. 8正确答案： B 11 . 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_。A. O(1) B. O(n) C. O(n*n) D. O(log2n)正确答案： B 14 . 在一个链式队列中，假定front和rear分别为队头和队尾指针，则判断队空的条件为_。A. front=rear B. front!=NULL C. rear!=NULL D. front=NULL正确答案： D 24 . 一个子串在包含它的主串中的位置是指（ ）。A. 子串的最后那个字符在主串中的位置 B. 子串的最后那个字符在主串中首次出现的位置 C. 子串的第一个字符在主串中的位置D. 子串的第一个字符在主串中首次出现的位置输入答案： D答题正确 34 . 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。A. 同义词之间发生冲突。 B. 非同义词之间发生冲突。 C. 同义词或非同义词之间发生冲突。D. 散列表“溢出”。正确答案： B 答题错误 37 . 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为()。A. 3 B. 4 C. 5D. 6输入答案： B答题正确 38 . 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为()。A. 2 B. 3 C. 4D. 5输入答案： C答题正确 39 . 从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为()。A. O(n) B. O(1) C. O(log2n) D. O(n*n)输入答案： C答题正确 42 . 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（ ）。A. 19.5 B. 20 C. 20.5 D. 21输入答案： C答题正确 43 . 从有序表(12,18,30,43,56,78,82,95)中分别折半查找56元素时，其比较次数分别为（ ）。A. 1 B. 2 C. 3D. 4正确答案： C 7 . 在一个长度为n的顺序表中向第i个元素(0 irLink=s; s-lLink=p; p-rLink-lLink=s; s-rLink=p-rLink; B. s-lLink=p; s-rLink=p-rLink; p-rLink=s; p-rLink-lLink=s; C. p-rLink=s; p-rLink-lLink=s; s-lLink=p; s-rLink=p-rLink;D. s-lLink=p; s-rLink=p-rLink; p-rLink-lLink=s; p-rLink=s;输入答案： D答题正确 17 . 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）A. 3，2，6，1，4，5 B. 3，4，2，1，6，5 C. 1，2，5，3，4，6 D. 5，6，4，2，3，1正确答案： B D25 . 广义表C（A，B,（）的表头是 ( )A. C B. () C. AD. B输入答案： C答题正确 26 . 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。A. 4 B. 5 C. 6D. 7正确答案： C 27 . 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ ）个。A. 15 B. 16 C. 17D. 47输入答案： B答题正确 30 . 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ ）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙输入答案： B答题正确 33 . 设散列空间为到，为表项的关键码，散列函数采用除留余数法，即Hash（k）=k%p。为了减少发生冲突的频率，一般取p为（ ）。A. m B. 小于m的最大质数 C. 大于m的最小质数 D. 小于m的最大合数输入答案： B答题正确 34 . 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。A. 同义词之间发生冲突。 B. 非同义词之间发生冲突。 C. 同义词或非同义词之间发生冲突。D. 散列表“溢出”。输入答案： B答题正确 35 . 下列广义表用链表来表示时，分支结点最多的是（ ）A. L=(x,(a,B),(x,(a,B),y) B. A=(s,(a,B) C. B=(x,(a,B),y) D. D=(a,B),(c,(a,B),D)正确答案： A 44 . 对线性表进行折半搜索时，要求线性表必须（ ）。A. 以数组方式存储。 B. 以数组方式存储且结点按关键码有序排列 C. 以链接方式存储。D. 以链接方式存储且结点按关键码有序排列。正确答案： A 19 . 设有一个递归算法如图，正确的叙述是（）A. maze(1020,10,7)=356 B. maze(352,4,11)=16214 C. maze(16,2,2)=8 D. 以上三个答案都不对正确答案： B 35 . 采用线性探查法解决冲突时所产生的一系列后继散列地址（ ）。A. 必须大于等于原散列地址。 B. 必须小于等于原散列地址。 C. 可以大于或小于原散列地址。D. 对地址在何处没有限制。输入答案： C答题正确 37 . 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为()的9分之一。A. 20 B. 18 C. 25D. 22正确答案： C 41 . 对一棵二叉搜索树进行（ ）遍历时，得到的结点序列是一个有序序列。A. 前序 B. 中序 C. 后序 D. 层次正确答案： B 38 . 从有序表(12,18,30,43,56,78,82,95)中分别折半查找56元素时，其比较次数分别为（ ）。A. 1 B. 2 C. 3D. 4正确答案： C 17 . 向一个栈顶指针为top的链式栈中插入一个s结点时，应执行_。A. top-link=s; B. s-link=top; top =s; C. s-link=top-link; top-link=s;D. s-link=top; top=top-link;输入答案： C正确答案： B 答题错误15 . 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_。A. O(1) B. O(n) C. O(n*n) D. O(log2n)输入答案： D正确答案： B 答题错误8 . 在下面程序段中，s=s+p语句的执行次数为：（ ）A. n2 B. n2/2 C. n（n+1）D. n(n+1)/2 E. n F. n/2输入答案： D正确答案： E 答题错误25 . 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为（）。A. SA+141 B. SA+144 C. SA+222D. SA+225输入答案： D正确答案： C 答题错误30 . 假定一棵三叉树的结点数为50，则它的最小高度为（）。A. 3 B. 4 C. 5D. 6输入答案： D正确答案： C 答题错误34 . 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ ）。A. 中序 B. 前序 C. 后序 D. 层次序输入答案： A正确答案： B 答题错误50 . 下列说法正确的有：（）A. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。B. 在二叉搜索树上插入新