设有n个待排序元素存放在一个不带表头结点的单链表中,每个链表结点只存放一个元素,头指针为r。
第1题
第2题
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大O表示法)?
第3题
对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为( ),所有邻接表中的结点总数为( )。
第5题
第6题
设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。
A.n-1
B.n
C.n+1
D.2n-1
第7题
设某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。
A.2n
B.n
C.n/2
D.n(n-1)
第9题
二叉搜索树中,然后对树进行中序遍历,并将元素按序放人数组a中,为简单起见,假设a中的数据互不相同。试编写一个函数,从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h),其中h是二叉搜索树的高度。
第10题
稀疏矩阵相加。两个稀疏矩阵A和B采用十字链表方式存储,计算C=A+B,C采用十字链表方式存储。
算法分析:根据矩阵相加的法则,C中的非零元素cij只可能有3种情况:aij+bij,aij(bij=0),bij(aij=0)。因此,当B加到A上时,对A的十字链表来说,或者是改变结点的val域值aij+bij≠0,或者不变(bij=0),或者插入一个新结点(aij=0),还可能是删除一个结点(aij+bij=0)。整个运算可从矩阵的第一行逐步进行。对每一行都从行表头出发分别找到A和B在该行中的第一个非零元素结点后开始比较,然后按以下4种不同情况分别处理(假设pa和pb分别指向A和B的十字链表中行值相同的两个结点)。
第11题
设有一个长度为S的字符串,其字符顺序存放在一个一维数组的第1至第S个单元中(每个单元存放一个字符)。现要求从此字符串的第m个字符以后删除长度为t的子串,m<s,t<(s-m),并将删除后的结果复制在该数组的第s单元以后的单元中,试设计此删除算法。