数据结构考试题与答案

数据结构考试题与答案一、单选题（共100题，每题1分，共100分）1、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是()A、108B、120C、110D、100正确答案：A2、散列查找中散列函数的值()散列地址的范围。A、在B、大于C、无关D、小于正确答案：A3、计算机算法必须具备输入、输出和（）等5个特性。A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、易读性、稳定性和安全性D、确定性、有穷性和稳定性正确答案：B4、一棵完全二叉树上有1001个结点，其中叶子结点的个数是()。A、254B、505C、501D、500正确答案：C5、在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为()A、4，4，3B、4，3，3C、3，3，4D、3，4，4正确答案：B6、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要比较()个结点。A、(n+1)/2B、(n-1)/2C、nD、n/2正确答案：A7、广度优先遍历类似于二叉树的（）。A、后序遍历B、中序遍历C、先序遍历D、层次遍历正确答案：D8、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（）。A、(rear+l)％n=frontB、rear==frontC、rear％n==frontD、front+l=rear正确答案：B9、用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是()A、线性探测法B、除留余数法C、折叠法D、平方取中法正确答案：A10、在计算机中表示数据时，数据的物理地址和逻辑地址相同并且是连续的，称其为（）。A、链式存储结构B、顺序存储结构C、逻辑结构D、鸟以上都对正确答案：B11、设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A、d，c，b，aB、a，b，c，dC、a，b，d，cD、c，d，a，b正确答案：D12、若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数()。A、3B、4C、2D、1正确答案：C13、关于存储相同数据元素的说法中正确的是（）A、链式存储比顺序存储难于扩充空间B、顺序存储比链式存储多占空间C、顺序存储和链式存储都要求占用整块存储空间D、顺序存储比链式存储少占空间正确答案：D14、在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1)位置插入一个新元素时需要从后向前移动()个元素A、n-i-1B、n-i+1C、iD、n-i正确答案：B15、若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（）A、层次遍历B、中根遍历C、先根遍历D、后根遍历正确答案：C16、在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为()A、n-iB、n-i+1C、ID、i+1正确答案：A17、链式栈与顺序栈相比，一个比较明显的优点是（）。A、删除操作更加方便B、插入操作更加方便C、通常不会出现栈满的情况D、不会出现栈空的情况正确答案：C18、衡量查找算法效率的主要标准是（）。A、元素的个数B、所需的存储量C、平均查找长度D、算法难易程度正确答案：C19、在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为()。A、13B、12C、79D、24正确答案：A20、for（i=0；i<m；i++）for（j=0；j<n；j++）A［i][j］=i*j；上面算法的时间复杂度为()A、O(m2)B、O(n2)C、O(m×n)D、O(m+n）正确答案：C21、除根结点外，树上每个结点()A、可有一个孩子、任意多个双亲B、只有一个孩子、一个双亲C、可有任意多个孩子、一个双亲D、可有任意多个孩子、任意多个双亲正确答案：C22、数据结构的定义为(D，S)，其中D是()的集合。A、算法B、数据元素C、数据操作D、逻辑结构正确答案：B23、除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）A、2倍B、3倍C、1/2倍D、1倍正确答案：A24、队和栈的主要区别是()A、所包含的运算个数不同B、逻辑结构不同C、限定插入和删除的位置不同D、存储结构不同正确答案：C25、栈的插入和删除操作在（）进行。A、栈顶B、栈底C、指定位置D、任意位置正确答案：A26、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）A、选择排序B、希尔排序C、插入排序D、归并排序正确答案：A27、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。A、log2n-1B、log2nC、log2(n+1)D、log2n+1正确答案：D28、设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。A、n-1B、nC、2n-1D、2n正确答案：A29、在一个非空二叉树的中序遍历序列中，根结点的右边（）。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树的上的部分结点D、只有左子树上的所有结点正确答案：A30、有8个结点的无向连通图最少有（）条边。A、7B、8C、5D、6正确答案：A31、设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列（）。A、A,B,C,D,EB、B,C,D,E,AC、E,A,B,C,DD、E,D,C,B,A正确答案：C32、设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。A、3B、4C、5D、1正确答案：B33、设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。A、n/2B、n(n-1)C、nD、2n正确答案：C34、在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）A、终端结点B、直接前趋C、直接后继D、开始结点正确答案：C35、在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（）个元素。A、iB、n-iC、n-i-1D、n-i+l正确答案：B36、某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF，则后序遍历序列为（）A、BDGCEFHAB、GDBECFHAC、BDGAECHFD、GDBEHFCA正确答案：D37、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A、O(n3)B、O(n)C、O(n2)D、O(n+e)正确答案：D38、在平均情况下速度最快的排序方法为（）。A、归并排序B、简单选择排序C、堆排序D、快速排序正确答案：D39、高度为5的完全二叉树中含有的结点数至少为()A、31B、17C、16D、32正确答案：C40、对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为（）A、(5，1，4，3，6，2，8，7)B、(8，7，6，5，4，3，2，1)C、(5，1，4，3，2，6，7，8)D、(5，1，4，3，2，6，8，7)正确答案：D41、含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（）A、n+2B、n+1C、nD、n-1正确答案：B42、3个结点可构成（）棵不同形态的二叉树。A、4B、3C、2D、5正确答案：D43、设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。A、p->next=p->next->nextB、p=p->nextC、p=p->next->nextD、p->next=p正确答案：A44、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A、有序表B、线性表C、栈D、队列正确答案：D45、为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为（）A、37B、62C、41D、5正确答案：A46、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。A、低B、不好说C、相同D、高正确答案：D47、将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（）A、2n-1B、n2C、2nD、n正确答案：D48、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排序操作，直到子序列为空或只剩下一个元素为止。这样的排序方法是（）。A、直接选择排序B、冒泡排序C、直接插入排序D、快速排序正确答案：D49、设有n个结点的二叉树上只有度为0和度为2的结点，则此二叉树中叶子结点数()。A、（n+1)/2B、n/2C、不能确定D、(n-1)/2正确答案：A50、设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）A、3B、1C、2D、4正确答案：B51、设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正确答案：A52、要解决散列引起的冲突问题，常采用的方法有()A、数字分析法、平方取中法B、二次探测法、链地址法C、二次探测法、平方取中法D、数字分析法、线性探测法正确答案：B53、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。A、s->next=rear；rear=s；B、rear->next=s；rear=s；C、s->next=front；front=s；D、front->next=s；front=s；正确答案：B54、引起循环队列队头位置发生变化的操作是()。A、入队B、出队C、取队尾元素D、取队头元素正确答案：B55、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（）。A、s->next=hs->next；hs->next=s；B、hs->next=s；C、s->next=hs；hs=s；D、s->next=hs；hs=hs->next；正确答案：C56、采用线性链表表示一个向量时，要求占用的存储空间地址（）。A、必须是连续的B、部分地址必须是连续的C、可连续可不连续D、一定是不连续的正确答案：C57、栈是一种操作受限的线性结构，其操作的主要特征是()A、先进先出B、后进先出C、进优于出D、出优于进正确答案：B58、在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为()A、归并排序B、插入排序C、希尔排序D、选择排序正确答案：D59、关于二叉树性质的描述，正确的是（）A、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子B、二叉树至少含有一个根结点C、二叉树若存在两个结点，则必有一个为根，另一个为左孩子D、二叉树结点的个数可以为0正确答案：D60、深度为5的二叉树至多有()个结点。A、31B、32C、16D、10正确答案：A61、用链表表示线性表的优点是（）。A、便于随机存取B、数据元素的物理顺序与逻辑顺序相同C、花费的存储空间比顺序表少D、便于插入与删除正确答案：D62、二叉树的第k层的结点数最多为().A、2k+1B、2^k-1C、2k-1D、2^(k-1)正确答案：D63、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为()A、p->next=s->next；s->next=q;B、q->next=s->next；s->next=p；C、s->next=q；p->next=s->next；D、s->next=p；q->next=s->next；正确答案：B64、在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（）对相邻元素之间的交换。A、n+1B、n-1C、n/2D、n正确答案：B65、下列排序算法中，在最好情况下，时间复杂度为O(n)的算法是()。A、归并排序B、快速排序C、冒泡排序D、选择排序正确答案：C66、从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A、线性结构和树型结构B、线性结构和图状结构C、树形结构D、线性结构正确答案：A67、在索引顺序表中查找一个元素，可用的且最快的方法是（）。A、用二分查找方法确定元素所在块，再用二分查找在相应块中查找B、用顺序查找方法确定元素所在块，再用二分查找在相应块中查找C、用顺序查找方法确定元素所在块，再用顺序查找在相应块中查找D、用二分查找方法确定元素所在块，再用顺序查找在相应块中查找正确答案：D68、下面关于线性表的叙述错误的是（）。A、线性表采用链式存储不必占用一片连续的存储空间B、线性表采用顺序存储便于插入和删除操作的实现C、线性表采用顺序存储必须占用一片连续的存储空间D、线性表采用链式存储便于插入和删除操作的实现正确答案：B69、图的深度、广度优先遍历算法分别类似于二叉树的()。A、层序遍历和先序遍历B、先序遍历和中序遍历C、后序遍历和中序遍历D、先序遍历和层序遍历正确答案：D70、对于一个线性表，若既要求能够进行较快地插入和删除，又要求存储结构能够得出数据元素之间的关系，则应该以()。A、链式存储B、散列方式存储C、顺序方式存储D、索引方式存储正确答案：A71、判定一个队列QU（最多元素为m0）为满队列的条件是()A、QU->front==QU->rearQU->front==(QU->rear+1)%m0B、QU->front==QU->rear+1C、QU->rear－QU->front==m0D、QU->rear－QU->front－1==m0正确答案：C72、如下陈述中正确的是（）A、串的长度必须大于0B、串是一种特殊的线性表C、串中元素只能是字母D、空串就是空白串正确答案：B73、具有35个结点的完全二叉树的深度为()A、6B、8C、7D、5正确答案：A74、栈和队列共同具有的特点是（）A、都是先进后出B、既能先进先出，也能先进后出C、只允许在端点进行操作运算D、都是先进先出正确答案：C75、在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是()。A、快速排序B、堆排序C、基数排序D、归并排序正确答案：B76、散列查找是由键值（）确定散列表中的位置，进行存储或查找。A、平方B、本身C、相反数D、散列函数值正确答案：D77、若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为()。A、13B、8C、12D、4正确答案：C78、在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。A、O(n2)B、O(n)C、O(1)D、O(log2n)正确答案：B79、下列关于线性表的叙述中，不正确的是()A、线性表的每一个结点有且仅有一个前趋和一个后继B、线性表是n个结点的有穷序列C、线性表结点间的逻辑关系是1:1的联系D、线性表可以为空表正确答案：A80、长度为12的按关键字有序的查找表，采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是()。A、Dec-37B、37/13C、Dec-49D、49/13正确答案：D81、若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（）A、单循环链表B、单链表C、双链表D、顺序表正确答案：D82、对n个元素进行直接插入排序时间复杂度为（）。A、O(log2n)B、O(n2)C、O(1)D、O(n)正确答案：B83、根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）。A、是完全二叉树B、不是完全二叉树C、是满二叉树D、是完全二叉树且是满二叉树正确答案：A84、有个顶点e条边的无向图G，它的邻接表中的表结点总数是()。A、eB、2nC、nD、2e正确答案：D85、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为()。A、A,B,C,D,E,FB、A,B,C,F,D,EC、A,B,D,C,E,FD、A,C,B,F,D,E正确答案：D86、将5个不同的数据进行排序，至多需要比较（）次。A、10B、25C、9D、8正确答案：A87、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A、数据元素的相邻地址表示B、数据元素在表中的序号表示C、指向后继元素的指针表示D、数据元素的值表示正确答案：C88、含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）A、3B、5C、4D、6正确答案：A89、已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A、48B、0C、1D、49正确答案：D90、链表不具有的特点是（）。A、可随机访问任一元素B、插入、删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性长度成正比正确答案：A91、栈上溢现象通常出现在（）A、链栈的入栈操作过程中B、顺序栈的入栈操作过程中C、顺序栈的出栈操作过程中D、链栈的出栈操作过程中正