Question

数据结构小问题 帮忙解释下

1.设哈希表长m=14,哈希函数H(key)=key%k11,表中已有4个结点：
addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7
其余地址为空
2.如果采用二次探测再散列处理冲突，关键字为49的结点的地址是（ D ）。
A. 8 B. 3 C. 5 D. 9
假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（ C ）
A． O(n) B．O(e) C．O(n+e) D．O(n*e)

Answer 1

Next只是一个取名啊,你自己可以随便取什么名字的.你取Pre都可以...只是这样取名字更直观一些.光看到这个变量而不看构造函数的话你可能不知道为什么,如果你看看构造函数参数表第二个参数(ListNode<Elem Type> *N = NULL),这是一个指向ListNode类型的指针,默认赋值为NULL,NULL就是空指针的意思(顺便回答你的第二个问题),这是系统指定的一个默认地址,代表你什么东西都没有指向.如果你构造函数没有第二个参数输入的话,系统就认为你指向NULL,就是什么也没有指向.同时注意看构造函数":"后面初始化了两个成员变量,其中第二个是Next(N), 表明用N来初始化你的Next,这下应该明白了吧.

current->Next = new ListNode(x, current -> Next);这条语句的意思是用x和current->Next作为参数构造一个新的结点,其中x赋值给Element,current->Next赋值给Next,同时把这个结点赋给current->Next,这个时候原来的current->Next的值就被这个新的值取代了.比如,你原来current存的值是1,current->Next是NULL(因为你下一个结点还没有创建呢),这条语句就是创建一个新的结点,假设x=2,这样你就创建了一个新的结点,存的值为2,指向原来的current->Next(注意是NULL),同时把它赋值给current->Next(注意这个current是存1那个结点),这样的结果就是原来那个结点的Next指向这个新建的存有2的结点.

希望我讲得还算明白,感觉讲得过绕了...

Answer 2

第一题：哈希表的定义（一组关键字通过哈希函数得到一段连续的地址），addr（15）=4，是通过15%11，即15除以11取余数4。
第二题：核心是哈希表处理冲突方法：开放地址法（二次探测再散列），你查查这个方法的思想，一两句话也解释不清楚
第三题：当做定理记吧！

Answer 3

addr(49)=4 冲突 采用二次探测发（平方探测法） 第一次：+-1 为 4 5 冲突 第二次 ：+ -4 9 可以 选D