资源描述：
《【在线】17春北航《算法与数据结构》在线作业二》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、~一、单选题（共25道试题，共100分。）V1.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。A.O（nloge）B.O（n+e）C.O(n*e)D.O(n的平方)2.以下二叉树说法错误的是A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好3.下述几种排序方法中,平均查找长度最小的是（）A.插入排序B.选择排序C.快速排序D.归并排序4.对于顺序表，以下说法错
2、误的是（）A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中5.队列的插入操作是在（）进行。A.队首B.队尾C.队前D.队后6.设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。A.连接B.模式匹配C.求子串D.求串长7.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是A.存储结点每个存储结点可以存放一个或一个以
3、上的数据元素B.数据元素之间关联方式的表示也就是逻辑结构的机内表示C.附加设施，如为便于运算实现而设置的“哑结点”等等D.一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级8.串的逻辑结构与（）的逻辑结构不同。~~~~A.线性表B.栈C.队列D.树9.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（）A.24B.25C.23D.无法确定10.向顺序栈中压入新元素时，应当（）。A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行
4、11.由两个栈共享一个向量空间的好处是（）。A.减少存取时间，降低下溢发生的机率B.节省存储空间，降低上溢发生的机率C.减少存取时间，降低上溢发生的机率D.节省存储空间，降低下溢发生的机率12.下述几种排序方法中,要求内存量最大的是（）。A.插入排序B.选择排序C.快速排序D.归并排序13.二分查找要求被查找的表是（）A.键值有序的链接表B.链接表但键值不一定有序C.键值有序的顺序表D.顺序表但键值不一定有序14.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。A.nB.2nC.n-1D.n+115.在有n个叶子结点的哈夫曼树中，其结
5、点总数为（）。A.不确定~~~~B.2nC.2n+1D.2n-116.设无向图的顶点个数为n，则该图最多有（）条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.017.一个加权的无向连通图的最小生成树（）。A.有一棵或多棵B.只有一棵C.一定有多棵D.可能不存在18.带头节点的单链表head为空的判定条件（）。A.head=NULLB.head->next=NULLC.head->next=headD.head!=head19.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是A.正确性算法应能正确地
6、实现预定的功能(即处理要求)B.易读性算法应易于阅读和理解以便于调试修改和扩充C.健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果D.高效性即达到所需要的时间性能20.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。A.HL=p;p->next=HL;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.p->next=HL->next;HL->next=p;21.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（）。A.79,46,
7、56,38,40,80B.84,79,46,38,40,56C.84,79,56,46,40,38D.84,56,79,40,46,3822.以下说法错误的是（）A.线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻~~~~B.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻C.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻D.线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素23.当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则退栈时，用（）语句修改top
8、指针。A.top++B.top=0C.top--D.top=N24.在线性表的散列存储中，若用m表示散列表的
