数据结构模拟试题和答案2.doc

《数据结构》模拟试题2 单项选择题 1．针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。 A．单链表 B．双链表 C．顺序表 D．单循环链表 2．链表所具备的特点是（ ）。 A．可以随机访问任一结点 B．占用连续的存储空间 C．插入删除元素的操作不需要移动元素结点 D．可以通过下标对链表进行直接访问 3．数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A．物理 B．逻辑 C．存储 D．逻辑与物理 4．设有一个长度为n的顺序表，要在第i个元素之前插入一个元素（也就是插入元素作为新表的第i个元素），则移动元素个数为（ ）。 A．n-i+1 B．n-i C．n-i-1 D．i 5．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是（ ）。 A．p=q-next B．p-next=q C．q-next=NULL D．p-next=q-next 6．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的植，则执行（ ）。 A．x=top-data; top=top?next; B．x=top-data; C．top=top-next; x=top-data; D．top=top-next; x=data; 7．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ ）。 A．f-next=s; f=s; B．s-next=r;r=s; C．r-next=s;r=s; D．s-next=f;f=s; 8．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是（ ）。 A．18 B．45 C．53 D．58 9．一棵有n个结点采用链式存储的二叉树中，共有（ ）个指针域为空。 A．n B．n+1 C．n-1 D．n-2 10．设一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。 A．n B．2n C．n-1 D．n+1 11．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ ）个结点。 A．30 B．20 C．21 D．23 12．已知如图1所示的一个图，若从顶点a出发，按深度优先有哪些信誉好的足球投注网站法进行遍历，则可能得到的一种顶点序列为（ ）。 A．abecdf B．acfebd C．aedfcb D．aebcfd bd b d f e c a 图1 V6 V6 V7 V1 V2 V3 V8 V4 V5 图3 13．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（ ）次比较后查找成功。 A．3 B．4 C．6 D．8 14．有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。 A．37/12 B．39/12 C．41/12 D．35/12 15．一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A．40，38，46，79，56，84 B．40，38，46，84，56，79 C．40，38，46，56，79，84 D．38，40，46，56，79，84 二、填空题 1．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为______ __结构。 2．结构中的数据元素存在 的关系称为树形结构。 3．求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为________和____ ____。 4．设有一个头指针为head的单向循环