数据结构热身题之选择题 - 考研论坛.htm

Data Structure Question

      border=0></A>&nbsp;<A 
      href="http://bbs.kaoyan.com/download.asp?topic=608118"><IMG 
      alt=将本帖子内容通过email打包下载 src="数据结构热身题之选择题 - 考研论坛.files/mailto.gif" 
      align=absMiddle border=0></A>&nbsp;<A 
      href="http://bbs.kaoyan.com/ubbmisc.asp?forum=%BC%C6%CB%E3%BB%FA&amp;action=getip&amp;topic=608118"><IMG 
      alt=管理员查看xiaolee的IP src="数据结构热身题之选择题 - 考研论坛.files/ip.gif" align=absMiddle 
      border=0></A>&nbsp;
      <HR>

      <DIV align=right></DIV>单项选择题 在下面备选答案中选出一个正确的，将其号码填在 上。<BR>表、栈、队 
      <BR>1．链表不具有的特点是　　　　。<BR>a. 可随机访问任一结点 b. 插入删除不需要移动元素<BR>c. 不必事先估计存储空间 d. 
      所需空间与线性表长度成正比<BR>2. 若线性表最常用的操作是存取第i个元素及其前趋的值，则采用 存储方式节省时间。 <BR>a. 单链表 b. 
      双链表 c. 单循环链表 d.顺序表<BR>3. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用 
      存储方式最节省运算时间。<BR>a. 单链表 b. 仅有头指针的单循环链表 c. 双链表 d. 仅有尾指针的单循环链表<BR>4. 
      链表最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用<BR>存储方式最省时间。<BR>a. 单链表 b. 双链表 c. 
      单循环链表 d. 
      带尾指针的单循环链表<BR>5.&nbsp;&nbsp;&nbsp;&nbsp;若某线性表最常用的操作是在存取任一指定序号的元素和在最后进行插入和删除运算，则采用 
      存储方式最省时间。<BR>a. 顺序表 b. 双链表 c. 带头结点的双循环链表 d. 单循环链表<BR>6. 
      一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是 。<BR>　 a. 23415 b. 54231 c. 23145 
      d.15432<BR>7. 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是 。<BR>a. 23415 b. 54132 c. 
      31245 d.14253<BR>8. 
      若用数组S[1..n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S[1..n]全满才不能作入栈操作。为这两个栈分配空间的最佳发方案是 
      。<BR>a. S1的栈底位置为0,S2的栈底位置为n+1 b. S1的栈底位置为0,S2的栈底位置为n/2<BR>c. 
      S1的栈底位置为1,S2的栈底位置为n d. S1的栈底位置为1,S2的栈底位置为n/2<BR>9. 队列操作的原则是 。<BR>a. 先进先出 
      b. 后进先出 c. 只能进行插入 d. 只能进行删除
      <P>串、数组、广义表<BR>1．串是　　　　。<BR>a. 不少于一个字母的序列 b. 任意个字母的序列<BR>c. 不少于一个字符的序列 d. 
      有限个字符的序列<BR>2. 串的长度是指串中 。<BR>a.不同字母的个数 b.不同字符的个数 c.所含字符的个数 
      d.所含字符的个数且大于0<BR>4. 用十字链表表示一个有k个非0元素的m*n的稀疏矩阵，则其总结点数为 。<BR>a. m*n b. 
      m*n+m+n c. k+max(m,n)+1 d. k+m+n+1 <BR>5. 对矩阵压缩存储是为了 。<BR>a. 方便运算 b. 节省空间 
      c. 方便存储 d. 提高运算速度
      <P>树、二叉树<BR>1. 
      对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于右孩子的编号，则可采用 
      次序的遍历实现编号。<BR>a.先序 b.中序 c.后序 
      d.从根开始的层次遍<BR>2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为　　　　。<BR>a. 
      98 b. 99 c. 50 d. 48<BR>3. 某二叉树的先序序列和后序序列刚好相反,则该二叉树一定是 的二叉树。<BR>a.空或只有一个结点 
      b.高度等于其结点数<BR>c.任一结点无左孩子 d.任一结点无右孩子<BR>4. 一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足 
      。<BR>a. 其中任意一结点均无左孩子 b. 其中任意一结点均无右孩子<BR>c. 其中只有一个叶子结点 d. 是任意一棵二叉树<BR>5. 
      有64个结点的完全二叉树的深度为 （根的层次为1）。<BR>a. 8 b. 7 c. 6 d. 5<BR>6. 
      在有n个结点的二叉链表中，值非空的链域的个数为 。<BR>a. n-1 b. 2n-1 c. n+1 d. 2n+1<BR>7. 
      一棵左右子树均不空的n个结点二叉树在先序线索化后，其空指针域个数为 。<BR>a. 0 b. 1 c. 2 d. 不确定<BR>8. 
      一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为 。<BR>a. 0 b. 1 c. 2 d. 不确定<BR>9. 
      判断线索二叉树中某结点P↑有左孩子的条件是 。<BR>　a. P≠nil b. P↑.lchild≠nil c. P↑.ltag=0 d. 
      P↑.ltag=1<BR>1．用n个键值构造一棵二叉排序树，最低高度为　 <BR>a. n/2 b. n c. 「Logn」　　 d. 
      「Logn+1」<BR>2. 在有n个叶子结点的哈夫曼树中，其结点总数为　　　　。<BR>1）不确定 2）2n 3）2n+1 4）2n-1
      <P>查找、排序<BR>4. 在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数为 。<BR>a.O(n) b. O( n) c. 
      O(n n) d. O( ) <BR>c. [gc,ax,eb,cd,bb]ff[da,ha] d. 
      [ax,bb,cd,da]ff[eb,gc,ha]<BR>7. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 
      。<BR>a.堆排序 b.冒泡排序 c.直接选择排序 d.快速排序<BR>8. 下列排序算法中时间复杂度不受数据初始状态影响，恒为O( )的是 
      。<BR>a.堆排序 b.冒泡排序 c.直接选择排序 d.快速排序<BR>9. 下列排序算法中， 
      算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。<BR>a.堆排序 b.冒泡排序 c.快速排序 d.希尔排序<BR>0. 
      若表R已在排序前已按键值递增顺序排列，则 算法的比较次数最少。<BR>a. 直接插入排序 b. 快速排序 c. 归并排序 d. 选择排序<BR>1. 
      下列排序算法中， 排序在某趟结束后不一定能选出一个元素放在其最终位置上。<BR>a. 选择 b. 冒泡 c. 归并 d. 堆<BR>2. 
      快速排序算法在最好情况下的时间复杂度为 。<BR>a.O(n) b.O( ) c.O(nlogn) d.O(logn)<BR>3. 
      快速排序算法在最好情况下的时间复杂度为 。<BR>a.O(n) b. O(n2) c. O(nlogn) d. O(logn)<BR>5. 
      下列排序算法中， 每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。<BR>a.&nbsp;&nbsp;&nbsp;&nbsp;冒泡排序 
      b.希尔排序 c.直接选择排序 d.直接插入排序<BR>6. 下列排序算法中，在待排序的数据表已经为有序时，反而花费时间最多的是 
      。<BR>a.快速排序 d.堆排序 c.冒泡排序 d.希尔排序<BR>7. 数据表有10000个元素，如果仅要求求出其中最大的10个元素则采用 
      最节省时间。<BR>a.堆排序 b.Shell排序 c.快速排序 d.直接选择排序<BR>8. 
      下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是 。<BR>　　 a.堆排序 b.冒泡排序 c.快速排序 d.希尔排序<BR>9. 
      下列排序算法中， 算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。<BR>a.堆排序 b.冒泡排序 c.快速排序 
      d.插入排序<BR>0. 下列排序算法中，每一趟都能选出一个元素放在其最终位置上，并且其时间性能受数据初始特性影响的是 。<BR>a. 直接插入排序 
      b. 快速排序 c. 直接选择排序 d. 堆排序<BR>1. 
      下列排序算法中，依次将待排序序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是 。<BR>a. 直接插入排序 b.冒泡排序 c. 快速排序 
      d. 直接选择排序<BR>2. 依次将待排序序列中的元素和有序子序列合并为一个新的有序序列的算法是 。<BR>a. 快速排序 b. 插入排序 
      c.冒泡排序 d. 堆排序<BR>3. 已知数据表A中每个元素距其最终位置不远，则采用 排序算法最节省时间。<BR>a. 堆排序 b. 插入排序 
      c. 快速排序 d. 直接选择排序 
      <P>图<BR>1. 带权有向图G用邻接矩阵A存储，则顶点 i 的入度等于A中第 i 。<BR>a. 行非∞的元素之和 b. 
      列非∞的元素之和<BR>c. 行非∞且非0的元素个数 d. 列非∞且非0的元素个数<BR>2. 在用邻接表表示图的情况下，拓扑排序算法的时间复杂度为 
      。<BR>a. O(n+e) b.O(n) c. O(n2) d. O(n3) e.O(n*e)<BR>3. 
      设图G采用邻接表存储，则拓扑排序算法的时间复杂度为 。<BR>　　 b. O(n+e) c.O(n2) d.O(n*e)<BR>4. 
      在图G用邻接矩阵/表存储时，求最短路径的Dijkstra算法的时间复杂度为 。<BR>　　 a.O(n) b.O(n+e) c.O(n2) 
      d.O(n*e) e. dO(n3)<BR>5. 求最短路径的Floyd算法的时间复杂度为 。<BR>a.O(n) b.O(n+e) c.O(n2) 
      d.O(n3)<BR>6．任何一个无向连通图的最小生成树　　　　。<BR>1）只有一棵 2）有一棵或多棵 3）一定有多棵 4）可能不存在<BR>
      <P>
      <HR>
      做人如果没梦想，那跟咸鱼有什么分别？ </TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
  <TBODY>
  <TR>
    <TD></TD>
    <TD align=right><A 
      href="http://bbs.kaoyan.com/newsDetail.asp?action=findthread&amp;Forum=%BC%C6%CB%E3%BB%FA&amp;go=newer&amp;id=608118">上一贴</A>&nbsp;|&nbsp;<A 
      href="http://bbs.kaoyan.com/newsDetail.asp?action=findthread&amp;Forum=%BC%C6%CB%E3%BB%FA&amp;go=older&amp;id=608118">下一贴</A></TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
  <TBODY>
  <TR>
    <TD align=middle><B>管理选项：</B><A 
      href="http://bbs.kaoyan.com/Posting.asp?action=CloseThread&amp;topic=608118&amp;topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%D1%A1%D4%F1%CC%E2&amp;Forum=%BC%C6%CB%E3%BB%FA">关闭主题</A>&nbsp;|&nbsp;<A 
      href="http://bbs.kaoyan.com/posting.asp?action=movetotop&amp;topic=608118&amp;topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%D1%A1%D4%F1%CC%E2&amp;forum=%BC%C6%CB%E3%BB%FA">置于顶部</A>&nbsp;|&nbsp;<A 
      href="http://bbs.kaoyan.com/archive.asp?action=transfer&amp;topic=608118&amp;topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%D1%A1%D4%F1%CC%E2&amp;forum=%BC%C6%CB%E3%BB%FA">移动/归档</A>&nbsp;|&nbsp;<A 
      href="http://bbs.kaoyan.com/posting.asp?action=deletepost&amp;topic=608118&amp;topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%D1%A1%D4%F1%CC%E2&amp;forum=%BC%C6%CB%E3%BB%FA">删除主题</A>&nbsp;</TD></TR>
  <TR>
    <TD>
      <P><A 
      href="http://bbs.kaoyan.com/posting.asp?action=newtopic&amp;forum=%BC%C6%CB%E3%BB%FA"><IMG 
      alt=新开主题 src="数据结构热身题之选择题 - 考研论坛.files/postnew.gif" 
      border=0></A>&nbsp;&nbsp;<A 
      href="http://bbs.kaoyan.com/posting.asp?action=reply&amp;topic=608118&amp;Forum=%BC%C6%CB%E3%BB%FA&amp;TopicSubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%D1%A1%D4%F1%CC%E2"><IMG 
      alt=回复该主题 src="数据结构热身题之选择题 - 考研论坛.files/replynew.gif" 
    border=0></A><BR></P></TD></TR></TBODY></TABLE>
<TABLE width="100%">
  <FORM name=jump action=jump.asp method=get>
  <TBODY>
  <TR>
    <TD vAlign=center align=right>
      <P><B>跳转到: </B><SELECT class=smallSel size=1 name=jumpTo><OPTION 
        value=default.asp>--- 考研交流 ---<OPTION 
        value=list.asp?GroupName=%CE%CA%CC%E2%C7%F3%BD%E2>&nbsp;&nbsp;&nbsp;&nbsp;问题求解<OPTION 
        value=list.asp?GroupName=%BF%BC%D1%D0%C2%E8%C2%E8>&nbsp;&nbsp;&nbsp;&nbsp;考研妈妈<OPTION 
        value=list.asp?GroupName=%D4%DA%D6%B0%BF%BC%D1%D0>&nbsp;&nbsp;&nbsp;&nbsp;在职考研<OPTION 
        value=list.asp?GroupName=%CA%D4%CC%E2%D6%D0%D0%C4>&nbsp;&nbsp;&nbsp;&nbsp;试题中心<OPTION 
        value=list.asp?GroupName=%BF%BC%D1%D0%CD%AC%B0%E9>&nbsp;&nbsp;&nbsp;&nbsp;考研同伴<OPTION 
        value=list.asp?GroupName=%B6%FE%CA%D6%CA%D0%B3%A1>&nbsp;&nbsp;&nbsp;&nbsp;二手市场<OPTION 
        value=list.asp?GroupName=%CD%AC%B5%C8%D1%A7%C1%A6>&nbsp;&nbsp;&nbsp;&nbsp;同等学力<OPTION 
        value=default.asp>--- 情感空间 ---<OPTION