计算机科学与技术自考本科02331自考数据结构(题库含答案)-

数据结构复习资料-2数据结构复习资料-202331数据结构单选题1.下列程序段的时间复杂度为(D)s=0；for(i=1；i<n；i++)for(j=1；j<n；j++)s+=i*j；A.O(1) B.O(n)C.O(2n) D.O(n2)2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是(B)A.head==NULL； B.head->next==NULL；C.head!=NULL； D.head->next==head；3.栈是一种操作受限的线性结构，其操作的主要特征是(B)A.先进先出 B.后进先出C.进优于出 D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为(B)A.(rear-front-1)％n B.(rear-front)％nC.(front-rear+1)％n D.(rear-front+n)％n5.判断两个串大小的基本准则是(D)52A.两个串长度的大小 B.两个串中首字符的大小C.两个串中大写字母的多少 D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为(C)A.1012 B.1017C.1034 D.10367.高度为5的完全二叉树中含有的结点数至少为(A)A.16 B.17C.31 D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为(C)A.5 B.8C.11 D.189.下列关键字序列中，构成大根堆的是(D)A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，310.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为(B)A. B.C. D.12.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的(A)。A.输入量 B.输出量C.数据 D.数据结构13.在双向循环链表中插入一个新的结点时，应修改(B)个指针域的值。A.1 B.4C.3 D.214.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现(B)个不同的出栈序列。A.4 B.5C.3 D.617.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有(B)棵。A.1 B.4C.3 D.218.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为(A)。A．15，12，11，10，8，16，18，17B．15，13，11，10，8，16，18，17C．15，12，19，10，8，16，18，17D．15，11，12，10，8，16，18，1721. 按值可否分解，数据类型通常可分为两类，它们是(C)A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型D.数组类型和指针类型22. 指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是(A)A.p->next=r；q->next=r->next；r->next=q；B.p->next=r；r->next=q；q->next=r->next；C.r->next=q；q->next=r->next；p->next=r；D.r->next=q；p->next=r；q->next=r->next；23. 若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是(B)A.3B.5C.6D.724. 假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为(D)A.rear==frontB.(front+1)％n==rearC.rear+1==frontD.(rear+1)％n==front27. 已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为(A)A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA29. 若非连通无向图G含有21条边，则G的顶点个数至少为(B)A.7B.8C.21D.2230. 对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为(C)A.(5，1，4，3，6，2，8，7)B.(5，1，4，3，2，6，7，8)C.(5，1，4，3，2，6，8，7)D.(8，7，6，5，4，3，2，1)34. 任意一棵完全二叉树中，度为1的结点数最多为(A)。A.1B.2C.3D.435. 在5阶B树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含(B)个关键字。A.1B.2C.3D.436. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是(A)的。A.稳定B.不稳定C.正确的D.错误的37.若一棵完全二叉树中某结点无左孩子，则该结点一定是(D)。A·度为1的结点 B·度为2的结点C·分支结点 D·叶子结点38.设有50000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(C)法。A.希尔排序 B.快速排序C.冒泡排序 D.基数排序39.设一个栈的输入序列为A，B，C，D，则借助一个栈所能得到的输出序列不可能是(D)A.ABCD B.DCBA C.ACDB D.DABC40.带头结点的头指针为h的循环单链表为空的判断条件是(C).h==NULL B.h->link==NULLC.h->link==h D.h!=NULL41.串是一种特殊的线性表，其特殊性体现在(B )。A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符42.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是(B)的二叉树。A·空或只有一个结点 B·高度等于其结点数C·任一结点无左孩子 D·任一结点无右孩子43.在一个单链表中，若要删除p结点的直接后继结点，则执行(C)A·q=p->link;q->link=p->link;free(q);B·q=p->link;p->link=q;free(q);C·q=p->link;p->link=q->link;free(q);D·q=p->link;q->link=p;free(q);44.以下排序方法中，稳定的排序方法是(D )。A·冒泡排序和希尔排序 B·快速排序和归并排序C·直接插入排序和堆排序 D·冒泡排序和归并排序45.对数据元素按照递增序进行排序。如果待排序的数据元素的初始状态是递增有序的，那么采用下列(D)方法进行排序速度最快。A·快速排序 B·堆排序 C·归并排序 D·冒泡排序46.以下说法正确的是(C)。A·空串与空格串是相同的 B·"data"是"DataStructure"的子串C·空串是零个字符组成的串D·空串长度等于147.用3个结点能构造(B)棵不同形态的二叉树。A.6B.5 C.4 D.348.下面关于线性表的叙述中，错误的是(D)。A.线性表的顺序存储结构必须占用一片地址连续的存储单元B.线性表的链式存储结构不必占用一片地址连续的存储单元C.线性表的顺序存储结构可以随机存取任一数据元素D.线性表的链式存储结构可以随机存取任一数据元素 49.下列几种排序方法中，键值总的比较次数和记录的初始排列无关的是(D)。A·起泡排序B·归并排序C·直接插入排序D·直接选择排序50.在一个单链表中的p结点之后插入一个新的q结点，则执行(A)。A.q->link=p->link;p->link=q; B.p->link=q;q->link=p->link;C.p->link=q->link;q->link=p;D.q->link=p;p->link=q->link;51.按照不同的顺序输入4，5，6三个关键字，能建立(B)棵不同的二叉排序树。A.6B.5 C.4 D.352.若线性表采用顺序存储结构存放，在长度为m的线性表中第i(1im)个数据元素之前插入一个新的数据元素需要移动(C)个数据元素。A.i B.m-i C.m-i+l D.m-i-153.串的模式匹配算法是指(C).A.判断两个串是否相等B.对两个串进行大小比较C.找某子串在主串中第一次出现的位置D.找某字符在主串中第一次出现的位置54.在线性表的下列4种运算中，(C)运算使用顺序存储结构比链式存储结构好。A.插入B.删除C.根据序号查找D.根据元素值查找56.具有n个顶点的简单无向图最多可包含(C)条边。A.n-1 B.n C.n(n-1)/2 D.n(n-1)57.某二叉树的后序序列和中序序列相同，则该二叉树一定是(D)的二叉树。A.空或只有一个结点 B.根结点无左孩子C.任一结点无左孩子 D.任一结点无右孩子58.线性表的链式存储结构的优点是(C)。A.便于随机存取 B.花费的存储空间比线性表的顺序存储结构少C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同59.判定一个有向图是否存在回路，可以利用（C)。A.求关键路径的方法 B.求最短路径的dijkstra方法C.拓扑排序算法 D.广度优先遍历算法60.3个结点能建立(C)棵不同形态的二叉树。A.3B.4C.5 D.661.高度为k(kl)的完全二叉树至少有(D)个结点。A.2k-1 B.2k C.2k-1+1 D.2k-163.线性单链表不具有的特点是(A )。A.可随机访问任一元素 B.插入删除不需要移动元素C.不必事先估计存储空间 D.所需空间与线性表长度成正比64.树的基本遍历策略有先根遍历和后根遍历；二叉树的基本遍历策略有先序遍历、中序遍历和后序遍历。则下列4种说法中正确的是（A）A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对67.设有序表{12,18,30,43,56,78,82,95}，用二分法查找56时，需要进行的比较次数为(B)。A.2B.3 C.4 D.568.将两个长度分别为m和n(1<m<n)的有序表合并成一个有序表，最少需要进行(A)次数据比较。A.m B.n C.m+n D.m*n69.已知一个栈的入栈序列是1，2，3，…，n，其出栈序列是p1，p2,p3,…，pn，若p1=n，则pi=(C)。A.i B.n-i C.n-i+l D.不确定70.具有n个叶子结点的哈夫曼树共有(B)个结点。A.2n B.2n-l C.2n+l D.n+l71.具有n个顶点的简单有向图最多可包含(D)条弧A.n-l B.n C.n(n-1)/2 D.n(n-1)73.图的广度优先搜索类似于树的(D)次序遍历A.先根 B.中根 C.后根 D.层次74.先序序列为ABC，后序序列为CBA的不同二又树有(C）棵A.2 B.3 C.4 D.575.若一个算法的时间复杂度用T(n)表示，其中n的含义是（A）A．问题规模 B．语句条数C．循环层数 D．函数数量76.具有线性结构的数据结构是（C）A．树 B．图C．栈和队列 D．二叉树77.将长度为n的单链表连接在长度为m的单链表（该单链表无尾指针）之后，其算法的时间复杂度为（B）A．O(1) B．O(m)C．O(n) D．O(m+n)78.在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（C）A．2个 B．3个C．4个 D．6个79.假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（B）A．3B．37C．50 D．9780.若线性表采用链式存储结构，则下列说法中正确的是（B）A．需要判断线性表满且需要判断线性表空B．不需要判断线性表满但需要判断线性表空C．需要判断线性表满但不需要判断线性表空D．不需要判断线性表满也不需要判断线性表空81.若串str=”Software”，其子串的数目是（D）A．8B．9C．36 D．3782.设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（C）A．1012 B．1017C．1032 D．103984．下列数据结构中，不属于二叉树的是（A）A．B树 B．AVL树C．二叉排序树 D．哈夫曼树85．下列排序算法中不稳定的是（A）A．快速排序 B．归并排序C．冒泡排序 D．直接插入排序86．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（B）A．2B．3C．4 D．888.数据常用的四种存储结构是(A)A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构89.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是(C)A.无头结点的单向链表 B.带头结点的单向链表C.带头结点的双循环链表 D.带头结点的单循环链表90.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是(B)A.head=NULL B.head->next=NULLC.head!=NULL D.head->next!=head91.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是(D)A.n-i B.n-i+lC.n-i+2 D.无法确定92.串匹配算法的本质是(C)A.串复制 B.串比较C.子串定位 D.子串链接93.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a[1][1]为第一个元素，其存储地址为1，每个元素占一个字节空间，则a[8][5]的地址为(C)A.13 B.18C.33 D.4094.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B)A.树中没有度为2的结点 B.树中只有一个根结点C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树96.在图G中求两个结点之间的最短路径可以采用的算法是(A)A.迪杰斯特拉（DijkstrA．算法 B.克鲁斯卡尔（Kruskal）算法C.普里姆(Prim)算法 D.广度优先遍历(BFS)算法97.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B)A.不稳定的 B.稳定的C.基于交换的 D.基于选择的98.设有一组关键字(19,14,23,1，6，20,4，27,5，11,10,9)，用散列函数H(key)=key%13构造散列表，用链地址法解决冲突，散列地址为1的链中记录个数为(C)A.1 B.2C.3 D.4100.下列选项中与数据存储结构无关的术语是（D）A.顺序表 B.链表C.链队列 D.栈101.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（B）A.n-1 B.nC.2n-1 D.2n102.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（D）A.rear=(rear-1)%m; B.front=(front+1)%m;C.front=(front-1)%m; D.rear=(rear+1)%m;103.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（A）A.堆栈 B.多维数组C.队列 D.线性表104.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（C）A.求子串 B.串联接C.串匹配 D.求串长106.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（C）A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树C.高度为n的二叉树 D.存在度为2的结点的二叉树107.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（B）A.4 B.5C.7 D.8108.下列叙述中错误的是（C）A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次B.图的遍历可以采用深度优先遍历和广度优先遍历C.图的广度优先遍历只适用于无向图D.图的深度优先遍历是一个递归过程109.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={<V1，V2>，<V1，V3>，<V2，V3>，<V2，V4>，<V3，V4>}，图G的拓扑序列是（A）A.V1,V2,V3,V4 B.V1,V3,V2,V4C.V1,V3,V4,V2 D.V1,V2,V4,V3110.平均时间复杂度为O(nlogn)的稳定排序算法是（C）A.快速排序 B.堆排序C.归并排序 D.冒泡排序112.已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（D）A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68)C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83)116、在数据的逻辑结构中，树结构和图结构都是（A）A.非线性结构 B.线性结构C.动态结构 D.静态结构117.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（C）A.O（1） B.Ｏ（logn） C.O（n） D.O（n2）118.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（D）A.p1－＞next=p2－＞next;p2－＞next=p1－＞next;B.p2－＞next=p1－＞next;p1－＞next=p2－＞next;C.p=p2－＞next;p1－＞next=p;p2－＞next=p1－＞next;D.p=p1－＞next;p1－＞next=p2－＞next；p2－＞next=p;119.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（B）A.2个 B.3个C.4个 D.6个120.队列的特点是（D）A.允许在表的任何位置进行插入和删除B.只允许在表的一端进行插入和删除C.允许在表的两端进行插入和删除D.只允许在表的一端进行插入，在另一端进行删除124.已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为（C）A.470 B.471 C.472 D.473125.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（B）A.12 B.16 C.18 D.20126.在带权图的最短路径问题中，路径长度是指（D）A.路径上的顶点数 B.路径上的边数C.路径上的顶点数与边数之和 D.路径上各边的权值之和127.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（C）A.e B.2e C.n2-2e D.n2-1128.要以O（nlogn）时间复杂度进行稳定的排序，可用的排序方法是（A）A.归并排序 B.快速排序C.堆排序 D.冒泡排序129.若希望在1000个无序元素中尽快求得前10个最大元素，应借用（A）A.堆排序 B.快速排序 C.冒泡排序 D.归并排序130.对有序表进行二分查找成功时，元素比较的次数（B）A.仅与表中元素的值有关 B.仅与表的长度和被查元素的位置有关C.仅与被查元素的值有关 D.仅与表中元素按升序或降序排列有关132.每个结点有且仅有一个直接前趋和多个(或无)直接后继(第一个结点除外)的数据结构称为（A）A.树状结构 B.网状结构C.线性结构 D.层次结构133.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（D）A.单链表 B.双链表C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表134.下面关于串的叙述中，正确的是（A）A.串是一种特殊的线性表B.串中元素只能是英文字母C.空串就是空白串 D.串的长度必须大于零135.无向完全图G有n个结点，则它的边的总数为（C）A.n2 B.n(n-1)C.n(n-1)/2 D.(n-1)136.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（B）A.9 B.11C.15 D.不确定137.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是（D）A.快速排序 B.归并排序C.冒泡排序 D.直接选择排序138.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是（C）A.按层遍历 B.前序遍历C.中序遍历 D.后序遍历140.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，9，-1，8，20，7，15)，则采用的排序方法是（C）A.选择 B.快速C.希尔 D.冒泡141.下述编码中不是前缀码的是（B）A.(00，01，10，11) B.(0，1，00，11)C.(0，10，110，111) D.(1，01，000，001)142.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+l，则x进栈的正确操作是（A）A.top=top-1；V[top]=x B.V[top]=x；top=top+1C.top=top+1；V[top]=x D.V[top]=x；top=top-1143.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是（D）A.p->data=-1 B.p->next=NULLC.p->next->next=head D.p->next=head144．一个算法的时间耗费的数量级称为该算法的（D）A．效率 B．难度C．可实现性 D．时间复杂度145．顺序表便于（D）A．插入结点 B．删除结点C．按值查找结点 D．按序号查找结点146．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是（B）A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL147．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为（A）A．(rear-front+m)％m B．rear-front+1C．(front-rear+m)％m D．(rear-front)％m148．下列关于顺序栈的叙述中，正确的是（A）A．入栈操作需要判断栈满，出栈操作需要判断栈空B．入栈操作不需要判断栈满，出栈操作需要判断栈空C．入栈操作需要判断栈满，出栈操作不需要判断栈空D．入栈操作不需要判断栈满，出栈操作不需要判断栈空149．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a[0][0]的存储地址为1，每个元素占一个存储单元，则a7,5的地址为（D）A．25 B．26C．33 D．34150．树的后序遍历等价于该树对应二叉树的（C）A．层次遍历 B．前序遍历C．中序遍历 D．后序遍历151．使用二叉线索树的目的是便于A．二叉树中结点的插入与删除 B．在二叉树中查找双亲C．确定二叉树的高度 D．查找一个结点的前趋和后继152．设无向图的顶点个数为n，则该图边的数目最多为（B）A．n-l B．n(n-1)／2C．n(n+1)／2 D．n2153．可进行拓扑排序的图只能是（C）A．有向图 B．无向图C．有向无环图 D．无向连通图154．下列排序方法中稳定的是（A）A．直接插入排序 B．直接选择排序C．堆排序 D．快速排序155．下列序列不为堆的是（C）A．75,45,65,30,15,25 B．75,65,45,30,25,15C．75,65,30,l5,25,45 D．75,45,65,25,30,15156．对线性表进行二分查找时，要求线性表必须是（C）A．顺序存储 B．链式存储C．顺序存储且按关键字有序 D．链式存储且按关键字有序157．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是（A）A．(4,1,2,3,5) B．(4,2,3,l,5)C．(4,5,2,1,3) D．(4,2,1,5,3)158．下列关于m阶B树的叙述中，错误的是（A）A．每个结点至多有m个关键字B．每个结点至多有m棵子树C．插入关键字时，通过结点分裂使树高增加D．删除关键字时通过结点合并使树高降低159．数据的逻辑结构可以分为（C）A．动态结构和静态结构 B.顺序结构和链式结构C．线性结构和非线性结构 D.简单结构和构造结构160．线性表是一个有限序列，组成线性表的基本单位是（B）A．数据项 B.数据元素C．数据域 D.字符161．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可能的出栈序列是（C）A．dcba B.cbdaC．cadb D.cdba162．稀疏矩阵的三元组表是（A）A．顺序存储结构 B.链式存储结构C．索引存储结构 D.散列表存储结构164．下列编码集合中，属于前缀编码的一组是（B）A.{11,10,001,101,0001} B.{00,010,0110,1000}C.{11,01,001,0101,0001} D.{0,10,110,1011}165．有向图中所有顶点入度之和与所有顶点出度之和的比是（B）A．1/2 B.1C．2 D.4166．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是（D）A.e B.2eC.n2-2e D.n2-e167.n个顶点的无向连通图，其生成树的边数为（A）A.n-l B.nC.n+l D.nlogn168．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为（C）A．2 B.3C．4 D.5169．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是（A）A.(13,44,55,26,8,29) B.(13,26,55,44,8,29)C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)170．采用分块查找时，要求数据（B）A．块内有序 B.分块有序C．分块无序 D.每块中数据个数必须相同171.下列关于散列函数的说法正确的是（D）A．散列函数越复杂越好B．散列函数越简单越好C．用除余法构造的散列函数是最好的D．在冲突尽可能少的情况下，散列函数越简单越好172．算法的时间复杂度表征的是（C）A．算法的可读性 B．算法的难易程度C．执行算法所耗费的时间 D．执行算法所耗费的存储空间173．对需要频繁插入和删除结点的线性表，适合的存储方式是（B）A．顺序储存 B．链式存储C．索引存储 D．散列存储174．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是（B）A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL175．迪杰斯特拉(Dijkstra)算法的功能是（A）A．求图中某顶点到其他顶点的最短路径 B．求图中所有顶点之间的最短路径C．求图的最小生成树 D．求图的拓扑排序序列176．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是（B）A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，1177．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1000，若每个元素占2个字节，则元素A[3][3]的存储地址为（D）A．1015 B．1016C．1028 D．1030178．深度为4的完全二叉树的结点数至少为（B）A．4 B．8C．13 D．15179．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中（B）A．结点k对应行元素之和 B．结点k对应列元素之和C．结点k对应行和列元素之和 D．非零元素之和180．无向图G的邻接矩阵一定是（A）A．对称矩阵 B．对角矩阵C．三角矩阵 D．单位矩阵181．下列关于有向带权图G的叙述中，错误的是（D）A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的182．在下列排序算法中，关键字比较次数与初始排列次序无关的是（D）A．冒泡排序 B．希尔排序C．直接插入排序 D．直接选择排序183．下列线性表中，能使用二分查找的是（C）A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25)C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89)184．在下列查找方法中，平均查找长度与结点数量无直接关系的是（C）A．顺序查找 B．分块查找C．散列查找 D．基于B树的查找185．下列排序算法中，时间复杂度为O(nlog2n)的算法是（A）A．快速排序 B．冒泡排序C．直接选择排序 D．直接插入排序186.与数据存储结构无关的概念是（A）A.栈 B.链表C.顺序表 D.二叉链表187.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是（B）A.1010 B.1016C.1018 D.1019188.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是（B）A.2 B.3C.4 D..6189.下列关于队列的叙述中,错误的是（D）A.队列是一种先进先出的线性表B.队列是一种后进后出的线性表C.循环队列中进行出队操作时要判断队列是否为空D.在链队列中进行入队操作时要判断队列是否为满190.对稀疏矩阵进行压缩存储的目的是（B）A.便于运算 B.节省存储空间C.便于输入输出 D.降低时间复杂度191.一棵二叉树的第7层上最多含有的结点数为（B）A.14 B.64C.127 D.128192.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是（C）A.n×e B.eC.2e D.n+e193.无向图中所有顶点的度数之和与所有边数之比是（C）A.1/2 B.1C.2 D.4194.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为（C）A.O（n） B.O（n+e）C.O（n2） D.O（n3）195.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是（D）A.归并排序 B.快速排序C.直接选择排序 D.冒泡排序196.比较次数与待排序列初始状态无关的排序方法是（D）A.快速排序 B.冒泡排序C.直接插入排序 D.直接选择排序198.下列关于m阶B树的叙述中,错误的是（D）A.根结点至多有m棵子树B.所有叶子都在同一层次上C.每个非根内部结点至少有ceil(m/2)棵子树D.结点内部的关键字可以是无序的200．下列选项中，不属于线性结构的是（A）A．网B．栈C．队列D．线性表201．长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为（B）A．n—iB．n—i—lC．iD．i+1203．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是（A）A．顺序栈需要判定栈空，链栈也需要判定B．顺序栈需要判定栈空，而链栈不需要判定C．顺序栈不需要判定栈空，而链栈需要判定D．顺序栈不需要判定栈空，链栈也不需要判定204．若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是（C）A．top=top+1；V[top]=xB．V[top]=x；top=top+1C．top=top一1；V[mp]=xD．V[top]=x；top=top—l205．在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先连续存放，则元素a[8][5]的起始地址是（D）A．SA+141B．SA+144C．SA+222D．SA+255207．一棵左子树为空的二叉树在前序线索化后，其空指针域个数为（C）A．0B．1C．2D．不确定208．下列关于哈夫曼树的叙述中，错误的是（A）A．用n个结点构造的哈夫曼树是唯一的B．哈夫曼树中只有度为0或度为2的结点C．树中两个权值最小的结点可能是兄弟结点D．同一结点集构造的二叉树中，哈夫曼树的WPL最小209．6个顶点的强连通图中，含有的边数至少是（C）A．4B．5C．6D．7210．有向图采用邻接矩阵存储，某一行中非零元素的个数等于（B）A．对应顶点v的度B．对应顶点v的出度C．对应顶点v的入度D．依附于对应顶点v的边数211．下列选项中，符合堆定义的是（C）A．{102，24，55，60，89，93}B．{24，89，55，60，93，102}C．{102，93，55，60，89，24}D．{102，60。89，93，55，24}212．已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为（D）A．{25，51，66，82，98，108}B．{25，51，66，98，82，108}C．{51，25，66，108，98，82}D．{51，25，66，82，98，108}213．下列选项中，其平均查找性能与基于二叉排序树的查找相当的是（A）A．二分查找B．顺序查找C．分块查找D．索引顺序查找214.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（C）A.栈B.队列C.树D.图215.m阶B-树中所有非终端结点(根结点除外)中的关键字个数必须大于或等于（C）A.m/2+1B.m/2 C.m/2-1 D.m216.在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（A）A.p->next==headB.p->next->next==headC.p->next==NULLD.p==head217.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（D．A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX218.两个字符串相等的条件是（D）A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同219．在数据结构中，从逻辑上可以把数据结构分为（C）A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构220．数据结构在计算机内存中的表示是指（A）A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系221.在数据结构中，与所使用的计算机无关的是数据的（A）结构。A.逻辑 B.存储 C.逻辑和存储D.物理222．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（C）A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法223．在决定选取何种存储结构时，一般不考虑（A）A．各结点的值如何B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。224．以下说法正确的是（D）A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构225．算法分析的两个主要方面是（A）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性226.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（D）A. 0B. 1C. 48D. 49229.在以下的叙述中，正确的是（B）A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出230.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（B）A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等231.链表不具备的特点是（A） A．可随机访问任一结点 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比232．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（C）A. 存储结构B. 逻辑结构C. 顺序存储结构D. 链式存储结构233.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储方式最节省运算时间是（D）A．单链表B．给出表头指针的单循环链表 C．双链表 D．带头结点的双循环链表234.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结（B）A．单链表B．静态链表C．线性链表D．顺序存储结构236.如果最常用的操作是取第i个结点及其前驱，则采用(D)存储方式最节省时间。单链表 B．双链表 C．单循环链表 D．顺序表237.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（B）A．O（1） B．O（n） C．O（n2） D．O（nlogn）238.在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行（B）操作与链表的长度有关。A．删除单链表中的第一个元素B．删除单链表中的最后一个元素C．在单链表第一个元素前插入一个新元素D．在单链表最后一个元素后插入一个新元素与单链表相比，双链表的优点之一是(D)A．插入、删除操作更简单B．可以进行随机访问C．可以省略表头指针或表尾指针D．顺序访问相邻结点更灵活240.如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（B）A．只有表头指针没有表尾指针的循环单链表B．只有表尾指针没有表头指针的循环单链表C．非循环双链表D．循环双链表241.在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n＋1），元素的移动次数为： （A）A．n–i＋1 B．n–iC．i D．i–1242.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(C) A．顺序表 B．用头指针表示的循环单链表C．用尾指针表示的循环单链表 D．单链表245.下述哪一条是顺序存储结构的优点? (C) A插入运算方便 B可方便地用于各种逻辑结构的存储表示C存储密度大 D删除运算方便246.下面关于线性表的叙述中，错误的是哪一个?（B）A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链式存储，不必占用一片连续的存储单元D线性表采用链式存储，便于进行插入和删除操作。247.线性表是具有n个（B）的有限序列。A．字符 B．数据元素 C．数据项 D．表元素248.在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（A）A．访问第i（1＜＝i＜＝n）个结点和求第i个结点的直接前驱（1＜i＜＝n）B．在第i（1＜＝i＜＝n）个结点后插入一个新结点C．删除第i（1＜＝i＜＝n）个结点D．以上都不对249.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）A．O（0） B．O（1） C．O（n） D．O（n^2）250.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度分别为（C）A．O（n）O（n） B．O（n）O（1） C．O（1）O（n）D．O（1）O（1）251.线性表（a1，a2， …，an）以链式方式存储，访问第i位置元素的时间复杂度为 （C）A．O（0） B．O（1） C．O（n） D．O（n2）251．单链表中，增加一个头结点的目的是为了（C） A．使单链表至少有一个结点 B．标识表结点中首结点的位置C．方面运算的实现 D．说明单链表是线性表的链式存储252下列各种数据结构中属于线性结构的有（A）A．栈B．二叉树C.广义表D．图253、与无向图相关的术语有（C）A．强连通图B．入度C．路径D．弧254、以下属于顺序存储结构优点的是（A）。A.存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示256、串的逻辑结构与（D）的逻辑结构不相同。A．线性表B．栈C．队列D．集合257、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（D）。A．上三角矩阵B．稀疏矩阵C.对角矩阵D．对称矩阵258、数据结构研究的内容是（D）。A．数据的逻辑结构B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面259、采用链结构存储线性表时，其地址（B）。A．必须是连续的B．连续不连续都可以C．部分地址必须是连续D．必须是不连续的260、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。当用二分查找法查找键值为84的结点时，经（B）比较后查找成功。A.4B.3C.2D.12261、二叉树第i(i≥1)层上至多有（C）结点。A．2iB．2iC．2i-1D．2i-1262、线性表的链接实现有利于（A）运算。A．插入B．读元素C．查找D．定位267、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A.单链表 B．仅有头指针的单循环链表C.双链表 D．仅有尾指针的单循环链表268、在数据结构中，从逻辑上可以把数据结构分为（C）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构269、数据结构中，在逻辑上可以把数据结构分成（B）。A．动态结构和静态结构B．线性结构和非线性结构C．紧凑结构和非紧凑结构D．内部结构和外部结构270、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（B）。A．loc(A1)+i*cB．loc(A1)+(i-1)*cC．loc(A1)+i*c+1D．loc(A1)+(i+1)*c271、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（A）。A．q->next=s;s->next=p;B．s->next=p->next;p->next=s;C．p->next=s->next;s->next=p D．p->next=s;s->next=q;272、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（B）A．3B．4C．5D．1273、链式存储的存储结构所占存储空间（A）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数274、队列的操作的原则是（A）。A．先进先出B．后进先出C.只能进行插入D．只能进行删除275、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（B）A．3，2，5，6，4，1B．1，5，4，6，2，3C．2，4，3，5，1，6D．4，5，3，6，2，1276、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（A）。A．p->next=p->next->nextB．p=p->nextC．p=p->nexe->nextD．p->next=p277、n个顶点，e条边的有向图的邻接矩阵中非零元素有（C）个。A．nB．2eC．eD．n+e278、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（D）存储方式最节省时间。A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表279、（C）在进行插入操作时，常产生假溢出现象。A．顺序栈B．循环队列C．顺序队列D．链队列280、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（C）。A.5，4，3，2，1，6 B．2，3，5，6，1，4C.3，2，5，4，1，6 D．1，4，6，5，2，3281.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（A）。A．直接选择排序B．直接插入排序C．快速排序D．起泡排序282、n个顶点的图的最小生成树必定（D），是不正确的描述。A．不唯一B．权的总和唯一C．不含回路D．有n条边283、n个顶点的强连通图至少有（A）条边。A．nB．n+1C．n-1D．n(n-1)284、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（C）。A．4B．5C．6D．7285、串的逻辑结构与（D）的逻辑结构不同。A．线性表B．栈C．队列D．树286、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是(B)A．9B．11C．15D．不能确定287、数据结构中，在逻辑上可以把数据结构分成（B）A．动态结构和静态结构B．线性结构和非线性结构C．紧凑结构和非紧凑结构D．内部结构和外部结构289、线性表的链接实现有利于（A）运算A．插入B．读元素C．查找D．定位290、数据结构中，在逻辑上可以把数据结构分成（B）A．动态结构和静态结构B．线性结构和非线性结构C．紧凑结构和非紧凑结构D．内部结构和外部结构291、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（A）。A．一个数量级别B．一个平均值C．一个最大值D．一个均方值292、下面程序段的时间复杂度是(A)。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;A．O(n^2)B．O(n)C．O(m*n)D．O(1)293、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a[1][1]为第一个元素，其存储地址为1，每元素占1个地址空间，则a[8][5]的地址为（B）。A．13B．33C．18D．40294、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（D）A．上三角矩阵B．稀疏矩阵C.对角矩阵D．对称矩阵295、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（A）A．直接选择排序B．直接插入排序C．快速排序D．起泡排序297、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（B）A.rear=rear->next; B．front=front->next;C.rear=front->next; D．front=rear->next;298、在数据结构中，从逻辑上可以把数据结构分为（C。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构299、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是(B)A．9B．11C．15D．不能确定300、队列的操作的原则是（A）。A．先进先出B．后进先出C.只能进行插入D．只能进行删除二、多选题1.以下说法正确的是（AD）A.二叉树的特点是每个结点至多只有两棵子树。B.二叉树的子树无左右之分。C.二叉树只能进行链式存储。D.树的结点包含一个数据元素及若干指向其子树的分支。2.算法设计的要求包括（ABC）A.正确性B.可读性C.健壮性D.确定性

3.下列属于算法的重要特征的是（ABCD）A.有穷性B.确定性C.可行性D.输入和输出4.图的四种存储结构（ABCD）A.邻接矩阵B.邻接表C.邻接多重表D.十字链表

5.依据所有数据成员之间的逻辑关系的不同，数据结构分为（AD）A.非线性结构B.逻辑结构C.物理结构D.线性结构

6.处理图的算法有（ACD）A.克鲁斯卡尔算法B.哈弗曼算法C.迪杰斯特拉算法D.拓扑排序算法7.下列说法正确的有（BCE）A.算法和程序原则上没有区别，在讨论数据结构时二者通用B.从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构C.所谓数据的逻辑结构是指数据元素之间的逻辑关系D.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据素所包含的数据项的个数相等E.数据的逻辑结构与数据元素本身的内容和形式无关8.关于线性表的特点下列描述正确的是（AC）A.存在唯一的一个被称作“第一个”的数据元素。B.不存在唯一的一个被称作“第一个”的数据元素。C.存在唯一的一个被称作“最后一个”的数据元素。D.不存在唯一的一个被称作“最后一个”的数据元素。

9.下面关于线性表的叙述正确的是（ABC）A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现

10.下列哪一条不是顺序存储结构的优点？（BCD）A.存储密度大B.插入运算方便C.可方便的用于各种逻辑结构的存储表示D.删除运算方便11.线性表的顺序存储结构是一种（AB）的存储结构A.随机存取B.顺序存取C.索引存取D.散列存取12.串是一种特殊的线性表，下列描述正确的是（ABCD）A.可以顺序存储B.数据元素是字符C.可以链式存储D.长度可以为0

13.下列存储形式中（